GATE CSE 1996 | Divide and Conquer Method Question 31 | Algorithms

Quicksort is run on two inputs shown below to sort in ascending order taking first element as pivot
i) 1, 2, 3,......., n
ii) n, n-1, n-2,......, 2, 1
Let C₁ and C₂ be the number of comparisons made for the inputs (i) and (ii) respectively. Then,

$$C_1 < C_2$$

$$C_1 > C_2$$

$$C_1 = C_2$$

we cannot say anything for arbitrary n

GATE CSE 1994

MCQ (Single Correct Answer)

-0.6

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

$$T(n) = 2T\left(\frac{n}{2}\right)+k, \text{ k is a constant }$$

$$T(n) = T\left(\frac{n}{2}\right)+k, \text{ k is a constant }$$

$$T(n) = T\left(\frac{n}{2}\right)+\log n$$

$$T(n) = T\left(\frac{n}{2}\right)+n$$

GATE CSE 1992

Subjective

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

Previous Next

Questions Asked from Marks 2

GATE CSE 2019 (1) GATE CSE 2018 (1) GATE CSE 2014 Set 1 (2) GATE CSE 2013 (2) GATE CSE 2012 (1) GATE CSE 2009 (2) GATE CSE 2008 (1) GATE CSE 2007 (1) GATE CSE 2006 (2) GATE CSE 2005 (1) GATE CSE 1997 (1) GATE CSE 1996 (2) GATE CSE 1994 (1) GATE CSE 1992 (1) GATE CSE 1987 (2)

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