1
GATE CSE 2008
MCQ (Single Correct Answer)
+2
-0.6
Consider the following functions: F(n) = 2n
G(n) = n!
H(n) = nlogn
Which of the following statements about the asymptotic behaviour of f(n), g(n), and h(n) is true?
A
f(n) = O (g(n)); g(n) = O(h(n))
B
f(n) = $$\Omega$$ (g(n)); g(n) = O(h(n))
C
g(n) = O (f(n)); h(n) = O(f(n))
D
h(n) = O (f(n)); g(n) = $$\Omega$$ (f(n))
2
GATE CSE 2008
MCQ (Single Correct Answer)
+2
-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?
A
$$\Theta \,(\log n)$$
B
$$\Theta \,(n)$$
C
$$\Theta \,(n\log n)$$
D
None of the above, as the tree cannot be uniquely determined.
3
GATE CSE 2007
MCQ (Single Correct Answer)
+2
-0.6
In the following C function, let n $$ \ge $$ m.
int gcd(n,m)
{
if (n % m == 0) return m;
n = n % m;
return gcd(m,n);
}
How many recursive calls are made by this function?
A
$$\Theta(\log_2n)$$
B
$$\Omega(n)$$
C
$$\Theta(\log_2\log_2n)$$
D
$$\Theta(\sqrt{n})$$
4
GATE CSE 2007
MCQ (Single Correct Answer)
+2
-0.6
What is the time complexity of the following recursive function?
int DoSomething(int n){
 if(n <= 2)
     return 1;
 else
     return (floor(sqrt(n)) + n);
}
A
$$\Theta \,({n^2})$$
B
$$\Theta \,(n\,{\log _2}\,n)$$
C
$$\Theta \,({\log _2}\,n)$$
D
$$\Theta \,({\log _2}\,{\log _2}\,n)$$
GATE CSE Subjects
Software Engineering
Web Technologies
EXAM MAP