1
GATE CSE 2009
MCQ (Single Correct Answer)
+2
-0.6
In quick sort, for sorting n elements, the (n/4)th smallest element is selected as pivot using an O(n) time algorithm. What is the worst case time complexity of the quick sort?
A
$$\Theta(n)$$
B
$$\Theta(n \log n)$$
C
$$\Theta(n^2)$$
D
$$\Theta(n^2 \log n)$$
2
GATE CSE 2008
MCQ (Single Correct Answer)
+2
-0.6
Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sub-lists each of which contains at least one-fifth of the elements. Let T(n) be the number of comparisons required to sort n elements. Then
A
$${\rm{T(n) < = 2T(n/5) + n}}$$
B
$$T\left( n \right){\rm{ }} < = {\rm{ }}T\left( {n/5} \right){\rm{ }} + {\rm{ }}T\left( {4n/5} \right){\rm{ }} + {\rm{ }}n$$
C
$$T\left( n \right){\rm{ }} < = {\rm{ }}2T\left( {4n/5} \right){\rm{ }} + {\rm{ }}n$$
D
$$T\left( n \right){\rm{ }} < = {\rm{ }}2T\left( {n/2} \right){\rm{ }} + {\rm{ }}n$$
3
GATE CSE 2007
MCQ (Single Correct Answer)
+2
-0.6
An array of n numbers is given, where n is an even number. The maximum as well as the minimum of these n numbers needs to be determined. Which of the following is TRUE about the number of comparisons needed?
A
At least 2n – c comparisons, for some constant c, are needed.
B
At most 1.5n – 2 comparisons are needed.
C
At least n log2 n comparisons are needed.
D
None of the above.
4
GATE CSE 2006
MCQ (Single Correct Answer)
+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{)}}$$
GATE CSE Subjects
Software Engineering
Web Technologies
EXAM MAP
Medical
NEET
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
CBSE
Class 12