GATE CSE 2013 | Complexity Analysis and Asymptotic Notations Question 18 | Algorithms

PREVIOUS NEXT

GATE CSE 2013

MCQ (Single Correct Answer)

-0.6

The number of elements that can be stored in $$\Theta (\log n)$$ time using heap sort is

$$\Theta (1)$$

$$\Theta (\sqrt {\log n} )$$

$$\Theta ({{\log \,n} \over {\log \,\log \,n}})$$

$$\Theta (\log n)$$

GATE CSE 2011

MCQ (Single Correct Answer)

-0.6

Which of the given options provides the increasing order of asymptotic Complexity of functions f₁, f₂, f₃ and f₄?
f₁ = 2ⁿ f₂ = n^3/2
f₃(n) = $$n\,\log _2^n$$
f₄ (n) = n^log₂n

f₃, f₂, f₄, f₁

f₃, f₂, f₁, f₄

f₂, f₃, f₁, f₄

f₂, f₃, f₄, f₁

GATE CSE 2008

MCQ (Single Correct Answer)

-0.6

You are given the post order traversal, P, of a binary search tree on the n element, 1,2,....,n. You have to determine the unique binary search tree that has P as its post order traversal. What is the time complexity of the most efficient algorithm for doing this?

$$\Theta \,(\log n)$$

$$\Theta \,(n)$$

$$\Theta \,(n\log n)$$

None of the above, as the tree cannot be uniquely determined.

GATE CSE 2008

MCQ (Single Correct Answer)

-0.6

Consider the following functions: F(n) = 2ⁿ
G(n) = n!
H(n) = n^logn
Which of the following statements about the asymptotic behaviour of f(n), g(n), and h(n) is true?

f(n) = O (g(n)); g(n) = O(h(n))

f(n) = $$\Omega$$ (g(n)); g(n) = O(h(n))

g(n) = O (f(n)); h(n) = O(f(n))

h(n) = O (f(n)); g(n) = $$\Omega$$ (f(n))

PREVIOUS NEXT