ExamSIDE.Com

# GATE CSE 1987 Question

Let P be a quicksort program to sort numbers in ascending order. Let t1 and t2 be the time taken by the program for the inputs [1 2 3 4] and [5 4 3 2 1], respectively. Which of the following holds?
A
t1 = t2
B
t1 > t2
C
t1 < t2
D
t1= t2 + 5 log 5

# GATE CSE 1987 Question

Find a solution to the following recurrence equation
T(n) = T(n - 1)+ n
T(1) = 1

# GATE CSE 1992 Question

Assume that the last element of the set is used as partition element in Quicksort. If n distinct elements from the set [1…n] are to be sorted, give an input for which Quicksort takes maximum time.

# GATE CSE 1994 Question

The recurrence relation that arises in relation with the complexity of binary search is:
A
$T(n) = 2T\left(\frac{n}{2}\right)+k, \text{ k is a constant }$
B
$T(n) = T\left(\frac{n}{2}\right)+k, \text{ k is a constant }$
C
$T(n) = T\left(\frac{n}{2}\right)+\log n$
D
$T(n) = T\left(\frac{n}{2}\right)+n$