GATE CSE 2019 | Searching and Sorting Question 3 | Algorithms

GATE CSE 2019

Numerical

-0.33

An array of 25 distinct elements is to be sorted using quicksort. Assume that the pivot element is chosen uniformly at random. The probability that the pivot element gets placed in the worst possible location in the first round of partitioning (rounded off to 2 decimal places) is ______.

Your input ____

GATE CSE 2016 Set 1

MCQ (Single Correct Answer)

-0.3

The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:

$$\Theta \left( {n\,\log n} \right),\Theta \left( {n\,\log n} \right),\,\,$$ and $$\,\,\Theta \left( {{n^2}} \right)$$

$$\Theta \left( {{n^2}} \right),\Theta \left( {{n^2}} \right),\,\,$$ and $$\,\,\Theta \left( {n\,\log n} \right)$$

$$\Theta \left( {{n^2}} \right),\,\,\Theta \left( {n\,\log n} \right),\,\,$$ and $$\,\,\Theta \left( {n\,\log n} \right)$$

$$\Theta \left( {{n^2}} \right),\Theta \left( {n\,\log n} \right),\,\,$$ and $$\,\,\Theta \left( {{n^2}} \right)$$

GATE CSE 2016 Set 2

MCQ (Single Correct Answer)

-0.3

Assume that the algorithms considered here sort the input sequences in ascending order. If the input is already in ascending order, which of the following are TRUE?

$$\,\,\,\,\,\,\,{\rm I}.\,\,\,\,\,\,\,$$ Quicksort runs in $$\Theta \left( {{n^2}} \right)$$ time
$$\,\,\,\,\,{\rm I}{\rm I}.\,\,\,\,\,\,\,$$ Bubblesort runs in $$\Theta \left( {{n^2}} \right)$$ time
$$\,\,\,{\rm I}{\rm I}{\rm I}.\,\,\,\,\,\,\,$$ Mergesort runs in $$\Theta \left( n \right)$$ time
$$\,\,\,{\rm I}V.\,\,\,\,\,\,\,$$ Insertion sort runs in $$\Theta \left( n \right)$$ time

$${\rm I}$$ and $${\rm II}$$ only

$${\rm I}$$ and $${\rm III}$$ only

$${\rm II}$$ and $${\rm IV}$$ only

$${\rm I}$$ and $${\rm IV}$$ only

GATE CSE 2015 Set 1

MCQ (Single Correct Answer)

-0.3

Which one of the following is the recurrence equation for the worst case time complexity of the Quicksort algorithm for sorting n ( $$ \ge 2$$ ) numbers? In the recurrence equations given in the options below, c is a constant.

T(n) = 2T(n/2) + cn

T(n) = T(n - 1) + T(1) + cn

T(n) = 2T(n - 1) + cn

T(n) = T(n/2) + cn

PREVIOUS NEXT