GATE CSE 2017 Set 1 | Complexity Analysis and Asymptotic Notations Question 15 | Algorithms

PREVIOUS NEXT

GATE CSE 2017 Set 1

MCQ (Single Correct Answer)

-0.33

Consider the following functions from positive integers to real numbers :

$10, \sqrt{n}, n, \log _2 n, \frac{100}{n}$.

The CORRECT arrangement of the above functions in increasing order of asymptotic complexity is :

$\log _2 n, \frac{100}{n}, 10, \sqrt{n}, n$

$\frac{100}{n}, 10, \log _2 n, \sqrt{n}, n$

$10, \frac{100}{n}, \sqrt{n}, \log _2 n, n$

$\frac{100}{n}, \log _2 n, 10, \sqrt{n}, n$

GATE CSE 2015 Set 3

MCQ (Single Correct Answer)

-0.3

Consider the equality $$\sum\limits_{i = 0}^n {{i^3}} = X$$ and the following choices for $$X$$
$$\eqalign{ & \,\,\,\,\,\,\,{\rm I}.\,\,\,\,\,\,\Theta \left( {{n^4}} \right) \cr & \,\,\,\,\,{\rm I}{\rm I}.\,\,\,\,\,\,\Theta \left( {{n^5}} \right) \cr & \,\,\,{\rm I}{\rm I}{\rm I}.\,\,\,\,\,\,O\left( {{n^5}} \right) \cr & \,\,\,{\rm I}V.\,\,\,\,\,\,\Omega \left( {{n^3}} \right) \cr} $$
The equality above remains correct if $$𝑋$$ is replaced by

Only $${\rm I}$$

Only $${\rm II}$$

$${\rm I}$$ or $${\rm III}$$ or $${\rm IV}$$ but not $${\rm II}$$

$${\rm II}$$ or $${\rm III}$$ or $${\rm IV}$$ but not $${\rm I}$$

GATE CSE 2013

MCQ (Single Correct Answer)

-0.3

What is the time complexity of Bellman-Ford single-source shortest path algorithm on a complete graph of n vertices?

$$\Theta ({n^2})$$

$$\Theta ({n^2}\log n)$$

$$\Theta ({n^3})$$

$$\Theta ({n^3}\log n)$$

GATE CSE 2013

MCQ (Single Correct Answer)

-0.3

Which one of the following is the tightest upper bound that represents the time complexity of inserting an object in to a binary search tree of n nodes?

O(1)

O(log n)

O(n)

O(n log n)

PREVIOUS NEXT