GATE CSE 2015 Set 3 | Complexity Analysis and Asymptotic Notations Question 9 | Algorithms

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 of the following is the tightest upper bound that represents the number of swaps required to sort n numbers using selection sort?

O(log n)

O(n)

O(n log n)

O(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)

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