1
GATE CSE 2006
+2
-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?
A
$$T\left( n \right){\rm{ }} = {\rm{ }}\theta \,{\rm{(loglogn)}}$$
B
$$T\left( n \right){\rm{ }} = {\rm{ }}\theta \,{\rm{(logn)}}$$
C
$$T\left( n \right){\rm{ }} = {\rm{ }}\theta \,{\rm{(}}\sqrt n {\rm{)}}$$
D
$$T\left( n \right){\rm{ }} = {\rm{ }}\theta \,{\rm{(}}n {\rm{)}}$$
2
GATE CSE 2006
+2
-0.6
The median of n elements can be found in O(n) time. Which one of the following is correct about the complexity of quick sort, in which median is selected as pivot?
A
$$\theta \,{\rm{(n)}}$$
B
$$\theta \,{\rm{(nlogn)}}$$
C
$$\theta \,{\rm{(n}}{}^2{\rm{)}}$$
D
$$\theta \,{\rm{(n}}{}^3{\rm{)}}$$
3
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)
4
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)$$
GATE CSE Subjects
EXAM MAP
Medical
NEET