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

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

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

An unordered list contains $$n$$ distinct elements. The number of comparisons to find an element in this list that is neither maximum nor minimum is