GATE CSE 2016 Set 2 | Searching and Sorting Question 5 | Algorithms

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

GATE CSE 2015 Set 3

MCQ (Single Correct Answer)

-0.3

Consider the following array of elements.

$$\,\,\,\,\,\,\,\,$$$$〈89, 19, 50, 17, 12, 15, 2, 5, 7, 11, 6, 9, 100〉$$

The minimum number of interchanges needed to convert it into a max-heap is

$$4$$

$$5$$