ExamSIDE.Com

© ExamSIDE.Com 2019

About Us Privacy Policy

GATE CSE 1987 Question

Signle Correct Answer
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

Subjective Type Answer by Yourself
Find a solution to the following recurrence equation
T(n) = T(n - 1)+ n
T(1) = 1

GATE CSE 1992 Question

Subjective Type Answer by Yourself
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

Signle Correct Answer
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$$

Share