GATE CSE 2020 | Complexity Analysis and Asymptotic Notations Question 11 | Algorithms

GATE CSE 2020

MCQ (Single Correct Answer)

-0.33

For parameters a and b, both of which are $$\omega \left( 1 \right)$$,
T(n) = $$T\left( {{n^{1/a}}} \right) + 1$$, and T(b) = 1.
Then T(n) is

$$\Theta \left( {{{\log }_a}{{\log }_b}n} \right)$$

$$\Theta \left( {{{\log }_{ab}}n} \right)$$

$$\Theta \left( {{{\log }_b}{{\log }_a}n} \right)$$

$$\Theta \left( {{{\log }_2}{{\log }_2}n} \right)$$

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

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)

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)$$