GATE CSE 2007 | Divide and Conquer Method Question 19 | Algorithms

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

GATE CSE 2005

MCQ (Single Correct Answer)

-0.6

Suppose T(n) = 2T (n/2) + n, T(0) = T(1) = 1
Which one of the following is FALSE?

T(n) = O(n²)

$$T\left( n \right){\rm{ }} = {\rm{ }}\theta \left( {n{\rm{ }}\,log\,{\rm{ }}n} \right)$$

$$T\left( n \right){\rm{ }} = {\rm{ }}\Omega ({n^2})$$

T(n) = O(n log n)