1

GATE CSE 1996

MCQ (Single Correct Answer)

+2

-0.6

The recurrence relation

T(1) = 2

T(n) = 3T(n/4) + n

has the solution, T(n) equals to

T(1) = 2

T(n) = 3T(n/4) + n

has the solution, T(n) equals to

2

GATE CSE 1994

MCQ (Single Correct Answer)

+2

-0.6

The recurrence relation that arises in relation with the complexity of binary search is:

3

GATE CSE 1992

Subjective

+2

-0

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.

4

GATE CSE 1987

MCQ (Single Correct Answer)

+2

-0.6

Let P be a quicksort program to sort numbers in ascending order. Let t

_{1}and t_{2}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?Questions Asked from Divide and Conquer Method (Marks 2)

Number in Brackets after Paper Indicates No. of Questions

GATE CSE Subjects

Theory of Computation

Operating Systems

Algorithms

Database Management System

Data Structures

Computer Networks

Software Engineering

Compiler Design

Web Technologies

General Aptitude

Discrete Mathematics

Programming Languages