1
GATE CSE 2011
MCQ (Single Correct Answer)
+2
-0.6
Which of the given options provides the increasing order of asymptotic Complexity of functions f1, f2, f3 and f4?
f1 = 2n f2 = n3/2
f3(n) = $$n\,\log _2^n$$
f4 (n) = n log2n
A
f3, f2, f4, f1
B
f3, f2, f1, f4
C
f2, f3, f1, f4
D
f2, f3, f4, f1
2
GATE CSE 2008
MCQ (Single Correct Answer)
+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];
}
f1(8) and f2(8) return the values
A
1661 and 1640
B
59 and 59
C
1640 and 1640
D
1640 and 1661
3
GATE CSE 2008
MCQ (Single Correct Answer)
+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})$$
4
GATE CSE 2008
MCQ (Single Correct Answer)
+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)$$
GATE CSE Subjects
Software Engineering
Web Technologies
EXAM MAP