GATE CSE 2008 | Divide and Conquer Method Question 18 | Algorithms

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

GATE CSE 2006

MCQ (Single Correct Answer)

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

$$\theta \,{\rm{(n)}}$$

$$\theta \,{\rm{(nlogn)}}$$

$$\theta \,{\rm{(n}}{}^2{\rm{)}}$$

$$\theta \,{\rm{(n}}{}^3{\rm{)}}$$

PREVIOUS NEXT