1
GATE CSE 2012
+2
-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
A
O(n log n)
B
O(n2 log n)
C
O(n2 + log n)
D
O(n2)
2
GATE CSE 2009
+2
-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?
A
$$\Theta(n)$$
B
$$\Theta(n \log n)$$
C
$$\Theta(n^2)$$
D
$$\Theta(n^2 \log n)$$
3
GATE CSE 2009
+2
-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?
A
$$\Theta(n)$$
B
$$\Theta(n \log n)$$
C
$$\Theta(n^2)$$
D
$$\Theta(n^2 \log n)$$
4
GATE CSE 2008
+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$$
GATE CSE Subjects
Theory of Computation
Operating Systems
Algorithms
Digital Logic
Database Management System
Data Structures
Computer Networks
Software Engineering
Compiler Design
Web Technologies
General Aptitude
Discrete Mathematics
Programming Languages
Computer Organization
EXAM MAP
Joint Entrance Examination