GATE CSE 2012 | Divide and Conquer Method Question 14 | Algorithms

GATE CSE 2012

MCQ (Single Correct Answer)

-0.6

A list of n strings, each of length n, is sorted into lexicographic order using the merge-sort algorithm. The worst case running time of this computation is

O(n log n)

O(n² log n)

O(n² + log n)

O(n²)

GATE CSE 2009

MCQ (Single Correct Answer)

-0.6

The running time of an algorithm is represented by the following recurrence relation:
$$T(n) = \begin{cases} n & n \leq 3 \\ T(\frac{n}{3})+cn & \text{ otherwise } \end{cases}$$
Which one of the following represents the time complexity of the algorithm?

$$\Theta(n)$$

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

$$\Theta(n^2)$$

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

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

PREVIOUS NEXT