1
GATE CSE 2004
MCQ (Single Correct Answer)
+2
-0.6
The time complexity of the following C function is (assume n > 0)
int recursive(int n){
 if(n == 1){
   return (1);
 }
 return (recursive(n - 1) + recursive(n - 1));
}
A
O(n)
B
O(n log n)
C
O(n2)
D
O(2n)
2
GATE CSE 2004
MCQ (Single Correct Answer)
+2
-0.6
Let A[1,...,n] be an array storing a bit (1 or 0) at each location, and f(m) is a function whose time complexity is O(m). Consider the following program fragment written in a C like language:
counter = 0;
for(i = 1; i <= n; i++){
 if(A[i]==1){
   counter++;
 }else{
   f(counter); counter = 0;
 }
}
The complexity of this program fragment is
A
$$\Omega ({n^2})$$
B
$$\Omega (n\,\log n)\,and\,O({n^2})$$
C
$$\theta (n)$$
D
$$O(n)$$
3
GATE CSE 2004
MCQ (Single Correct Answer)
+2
-0.6
What does the following algorithm approximate?
(Assume m > 1, $$ \in > 0$$)
x = m;
y = 1;
while(x - y > ε){
 x = (x + y) / 2;
 y = m/x;
}
print(x);
A
log m
B
m2
C
m1/2
D
m1/3
4
GATE CSE 2003
MCQ (Single Correct Answer)
+2
-0.6
The cube root of a natural number n is defined as the largest natural number m such that $${m^3} \le n$$. The complexity of computing the cube root of n (n is represented in binary notation) is
A
O(n) but not O(n0.5)
B
O(n0.5) but not O((log n)k) for any constant k > 0
C
O((log n)k) for some constant k > 0, but not O((log log n)m) for any constant m > 0
D
O((log log n)k) for some constant k > 0.5, but not O((log log n)0.5)
GATE CSE Subjects
Software Engineering
Web Technologies
EXAM MAP