GATE CSE 2011 | Complexity Analysis and Asymptotic Notations Question 24 | Algorithms

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

GATE CSE 2008

MCQ (Single Correct Answer)

-0.6

The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers is

$$\Theta \,(n)$$

$$\Theta \,({\log ^*}n)$$

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

$$\Theta \,(1)$$