GATE CS 2016 Set 2 Q13 — Searching, Sorting, Hashing

To determine which statements are true when the input sequence is already sorted in ascending order, let us analyze each sorting algorithm's behavior:

1. I. Quicksort runs in $\Theta(n^2)$ time:
   In the standard implementation of Quicksort (where the pivot is chosen as the first, last, or a fixed element), an already sorted array results in extremely unbalanced partitions at each step (one subproblem of size $0$ and another of size $n-1$). This yields the recurrence relation: $$T(n) = T(n-1) + \Theta(n)$$ Solving this gives a time complexity of $\Theta(n^2)$. Thus, Statement I is TRUE.


2. II. Bubblesort runs in $\Theta(n^2)$ time:
   An optimized version of Bubblesort uses a modified flag to check if any swaps were made during a pass. If the input is already sorted, the algorithm terminates after the first pass, requiring only $n-1$ comparisons and $0$ swaps. This results in a best-case time complexity of $\Theta(n)$. Thus, Statement II is FALSE.


3. III. Mergesort runs in $\Theta(n)$ time:
   Mergesort is a divide-and-conquer algorithm that always divides the array into two equal halves and merges them, regardless of the initial order of elements. Its recurrence relation is always: $$T(n) = 2T(n/2) + \Theta(n)$$ This results in a time complexity of $\Theta(n \log n)$ in all cases (best, worst, and average). Thus, Statement III is FALSE.


4. IV. Insertion sort runs in $\Theta(n)$ time:
   In Insertion Sort, each element is compared with its predecessor. Since the array is already sorted, each element (from index $1$ to $n-1$) is compared only once with the element immediately to its left and no shifts are needed. The total number of comparisons is $n-1$, which gives a best-case time complexity of $\Theta(n)$. Thus, Statement IV is TRUE.

Since statements I and IV are true, the correct option is D.