1
GATE CSE 2008
+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
+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 2008
+2
-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
A
$$\Theta \,(n)$$
B
$$\Theta \,({\log ^*}n)$$
C
$$\Theta \,({\log\,}n)$$
D
$$\Theta \,(1)$$
4
GATE CSE 2008
+2
-0.6
Consider the following C functions:
int f1(int n){
if(n == 0 || n == 1){
return n;
}
return (2 * f1(n - 1) + 3 * f1(n - 2));
}
int f2(int n){
int i;
int X[N], Y[N], Z[N];
X[0] = Y[0] = Z[0] = 0;
X[1] = 1; Y[1] = 2; Z[1] = 3;
for(i = 2; i <= n; i++){
X[i] = Y[i - 1] + Z[i - 2];
Y[i] = 2 * X[i];
Z[i] = 3 * X[i];
}
return X[n];
}

The returning time of f1(n) and f2(n) are
A
$$\Theta \,(n)\,and\,\Theta \,(n)$$
B
$$\Theta \,({2^n})\,and\,\Theta \,(n)$$
C
$$\Theta \,(n)\,and\,\Theta \,({2^n})$$
D
$$\Theta \,({2^n})\,and\,\Theta \,({2^n})$$
GATE CSE Subjects
EXAM MAP
Medical
NEET