Assume that the algorithms considered here sort the input sequences in…

Answer: Statements I and IV are true; Statements II and III are false.

Reasoning:

• Statement I (Quicksort runs in Θ(n²) time): True under the common classroom assumption that quicksort chooses a poor pivot deterministically (for example always choosing the first or last element). On an already sorted array that pivot choice leads to highly unbalanced partitions and the worst-case Θ(n²) behavior. If a randomized or more careful pivot selection is used, quicksort would instead run in Θ(n log n) on average, so pivot strategy matters.

• Statement II (Bubblesort runs in Θ(n²) time): False for the usual optimized version of bubble sort that checks whether any swaps occurred during a pass and stops early if the array is already sorted; that version has Θ(n) best-case time on already sorted input. A strictly unoptimized bubble implementation that always does all passes would be Θ(n²), but the common algorithm taught includes the early-exit optimization.

• Statement III (Mergesort runs in Θ(n) time): False. Mergesort performs divide-and-conquer merges that take Θ(n log n) time in all cases (best, average, and worst) because the divide depth is Θ(log n) and each level requires Θ(n) work.

• Statement IV (Insertion sort runs in Θ(n) time): True. Insertion sort performs a single pass with no shifts when the input is already sorted, giving Θ(n) best-case time.

Summary: Under the standard assumptions (naive pivot selection for quicksort, optimized bubble sort with early exit), the true statements for an already sorted input are that quicksort can be Θ(n²) and insertion sort is Θ(n); mergesort is Θ(n log n) and bubble sort is Θ(n) in its optimized form.