1
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$$
2
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.
3
GATE CSE 2006
MCQ (Single Correct Answer)
+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{)}}$$
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