1
GATE CSE 2005
+2
-0.6
Suppose T(n) = 2T (n/2) + n, T(0) = T(1) = 1
Which one of the following is FALSE?
A
T(n) = O(n2)
B
$$T\left( n \right){\rm{ }} = {\rm{ }}\theta \left( {n{\rm{ }}\,log\,{\rm{ }}n} \right)$$
C
$$T\left( n \right){\rm{ }} = {\rm{ }}\Omega ({n^2})$$
D
T(n) = O(n log n)
2
GATE CSE 1997
+2
-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?
A
$$T(n) = O \sqrt{n}$$
B
$$T(n)=O(n)$$
C
$$T(n) = O (\log n)$$
D
$$T(n) = O (\log n)$$
3
GATE CSE 1996
+2
-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 C1 and C2 be the number of comparisons made for the inputs (i) and (ii) respectively. Then,
A
$$C_1 < C_2$$
B
$$C_1 > C_2$$
C
$$C_1 = C_2$$
D
we cannot say anything for arbitrary n
4
GATE CSE 1996
+2
-0.6
The recurrence relation
T(1) = 2
T(n) = 3T(n/4) + n
has the solution, T(n) equals to
A
O(n)
B
O(log n)
C
O(n^3/4)
D
None of the above
GATE CSE Subjects
EXAM MAP
Medical
NEET