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
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)$$
3
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 = Y = Z = 0;
X = 1; Y = 2; Z = 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})$$
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 = Y = Z = 0;
X = 1; Y = 2; Z = 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];
}

f1(8) and f2(8) return the values
A
1661 and 1640
B
59 and 59
C
1640 and 1640
D
1640 and 1661
GATE CSE Subjects
Theory of Computation
Operating Systems
Algorithms
Digital Logic
Database Management System
Data Structures
Computer Networks
Software Engineering
Compiler Design
Web Technologies
General Aptitude
Discrete Mathematics
Programming Languages
Computer Organization
EXAM MAP
Joint Entrance Examination