Project ForgeAssume 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?
I. Quicksort runs in Θ(n²) time II. Bubblesort runs in Θ(n²) time III. Mergesort runs in Θ(n) time IV. Insertion sort runs in Θ(n) time
- AI and II only
- BI and III only
- CII and IV only
- I and IV only
Explanation
Quicksort with a naive first/last-element pivot degrades to its worst case Θ(n²) on already-sorted input (every partition is maximally unbalanced) — I is TRUE. Bubble sort with the standard early-termination optimization (stop once a full pass makes no swaps) finishes in a single Θ(n) pass on sorted input, not Θ(n²) — II is FALSE. Merge sort's divide-and-merge structure is entirely independent of input order — it is ALWAYS Θ(n log n), never Θ(n) — III is FALSE. Insertion sort on already-sorted input performs exactly one comparison per element with zero shifts, giving Θ(n) — IV is TRUE. So I and IV only.
Source: GATE CS 2016 (Session 2 / Set B) (2016)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.