Question 23

Evaluate the runtime of each algorithm when the input sequence of length $n$ is already in ascending order:

1. Statement I (Quicksort): Standard deterministic quicksort (with pivot selected as first or last element) partitions an already sorted array into sub-arrays of size $0$ and $n-1$. The recurrence is:
   $$T(n) = T(n-1) + \Theta(n) = \Theta(n^2)$$
   Thus, Statement I is TRUE.

2. Statement II (Bubblesort): With the standard early-termination flag (stopping if no swaps occur during a pass), an already sorted array requires only one pass of $n-1$ comparisons, running in $\Theta(n)$ time rather than $\Theta(n^2)$. Thus, Statement II is FALSE.

3. Statement III (Mergesort): Mergesort always divides the list into halves and merges them regardless of initial order:
   $$T(n) = 2T(n/2) + \Theta(n) = \Theta(n \log n)$$
   It never runs in $\Theta(n)$ time. Thus, Statement III is FALSE.

4. Statement IV (Insertion sort): For an already sorted array, each element $A[i]$ is compared only once with its predecessor $A[i-1]$ and no shifts are required. The inner loop terminates immediately, taking a total of $n-1$ comparisons, which is $\Theta(n)$ time. Thus, Statement IV is TRUE.

Therefore, Statements I and IV are TRUE. This corresponds to option (D).