GATE CSE 2006 | Divide and Conquer Method Question 21 | Algorithms

GATE CSE 2006

MCQ (Single Correct Answer)

-0.6

Consider the following recurrence:
$$T\left( n \right){\rm{ }} = {\rm{ 2T(}}\left\lceil {\sqrt n } \right\rceil {\rm{) + }}\,{\rm{1 T(1) = 1}}$$
Which one of the following is true?

$$T\left( n \right){\rm{ }} = {\rm{ }}\theta \,{\rm{(loglogn)}}$$

$$T\left( n \right){\rm{ }} = {\rm{ }}\theta \,{\rm{(logn)}}$$

$$T\left( n \right){\rm{ }} = {\rm{ }}\theta \,{\rm{(}}\sqrt n {\rm{)}}$$

$$T\left( n \right){\rm{ }} = {\rm{ }}\theta \,{\rm{(}}n {\rm{)}}$$

GATE CSE 2005

MCQ (Single Correct Answer)

-0.6

Suppose T(n) = 2T (n/2) + n, T(0) = T(1) = 1
Which one of the following is FALSE?

T(n) = O(n²)

$$T\left( n \right){\rm{ }} = {\rm{ }}\theta \left( {n{\rm{ }}\,log\,{\rm{ }}n} \right)$$

$$T\left( n \right){\rm{ }} = {\rm{ }}\Omega ({n^2})$$

T(n) = O(n log n)

GATE CSE 1997

MCQ (Single Correct Answer)

-0.6

Let T(n) be the function defined by $$T(1) =1, \: T(n) = 2T (\lfloor \frac{n}{2} \rfloor ) + \sqrt{n}$$
Which of the following statements is true?

$$T(n) = O \sqrt{n}$$

$$T(n)=O(n)$$

$$T(n) = O (\log n)$$

GATE CSE 1996

MCQ (Single Correct Answer)

-0.6

Quicksort is run on two inputs shown below to sort in ascending order taking first element as pivot
i) 1, 2, 3,......., n
ii) n, n-1, n-2,......, 2, 1
Let C₁ and C₂ be the number of comparisons made for the inputs (i) and (ii) respectively. Then,

$$C_1 < C_2$$

$$C_1 > C_2$$

$$C_1 = C_2$$

we cannot say anything for arbitrary n

PREVIOUS NEXT