GATE CSE 2009 | Divide and Conquer Method Question 17 | Algorithms

GATE CSE 2009

MCQ (Single Correct Answer)

-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?

$$\Theta(n)$$

$$\Theta(n \log n)$$

$$\Theta(n^2)$$

$$\Theta(n^2 \log n)$$

GATE CSE 2008

MCQ (Single Correct Answer)

-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

$${\rm{T(n) < = 2T(n/5) + n}}$$

$$T\left( n \right){\rm{ }} < = {\rm{ }}T\left( {n/5} \right){\rm{ }} + {\rm{ }}T\left( {4n/5} \right){\rm{ }} + {\rm{ }}n$$

$$T\left( n \right){\rm{ }} < = {\rm{ }}2T\left( {4n/5} \right){\rm{ }} + {\rm{ }}n$$

$$T\left( n \right){\rm{ }} < = {\rm{ }}2T\left( {n/2} \right){\rm{ }} + {\rm{ }}n$$

GATE CSE 2007

MCQ (Single Correct Answer)

-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?

At least 2n – c comparisons, for some constant c, are needed.

At most 1.5n – 2 comparisons are needed.

At least n log₂ n comparisons are needed.

None of the above.

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{)}}$$

PREVIOUS NEXT