GATE CSE 2004 | Complexity Analysis and Asymptotic Notations Question 36 | Algorithms

GATE CSE 2004

MCQ (Single Correct Answer)

-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

$$\Omega ({n^2})$$

$$\Omega (n\,\log n)\,and\,O({n^2})$$

$$\theta (n)$$

$$O(n)$$

GATE CSE 2004

MCQ (Single Correct Answer)

-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));
}

O(n)

O(n log n)

O(n²)

O(2ⁿ)

GATE CSE 2004

MCQ (Single Correct Answer)

-0.6

The recurrence equation
T(1) = 1
T(n) = 2T(n - 1)+n, $$n \ge 2$$
Evaluates to

2ⁿ⁺¹ - n - 2

2ⁿ - n

2ⁿ⁺¹ - 2n - 2

2ⁿ + n

GATE CSE 2003

MCQ (Single Correct Answer)

-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

O(n) but not O(n^0.5)

O(n^0.5) but not O((log n)^k) for any constant k > 0

O((log n)^k) for some constant k > 0, but not O((log log n)^m) for any constant m > 0

O((log log n)^k) for some constant k > 0.5, but not O((log log n)^0.5)

PREVIOUS NEXT