04-BS-16 · December 2013

Question 10 of 12: Insertion Sort — Best, Worst, and Big-O Complexity

Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)

Notes on this paper

National Examination, 04-BS-16 Discrete Mathematics, Dec 2013. Closed book, no aids, 3 hours, 12 questions of 10 marks each (100 marks); the exam instructs "answer 10 of 12" but every question is solved below as a complete study resource.

Reference texts: Rosen, Discrete Mathematics and Its Applications, 7th ed. (logic Ch.1, sets Ch.2, induction & pigeonhole Ch.5-6, relations Ch.9, counting Ch.6, discrete probability Ch.7, graphs Ch.10-11); Epp, Discrete Mathematics with Applications.

Question 10: Insertion Sort — Best, Worst, and Big-O Complexity (10 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. Insertion sort on a list of $n$ elements, best case (already sorted) and worst case (reverse-sorted).

Find. (a) A description of the algorithm. (b) Best-case comparison count. (c) Worst-case comparison count. (d) Overall worst-case complexity.

(a) How insertion sort works. Starting from the second element, insertion sort repeatedly takes the next unsorted element and shifts it leftward past every already-sorted element that is greater than it, inserting it into its correct position within the growing sorted prefix — much like sorting a hand of playing cards one at a time.
(b) Already-sorted list. For each of the $n-1$ new elements (positions $2,\dots,n$), it is compared exactly once to its immediate left neighbour, found to be already $\ge$, and left in place (no shifting needed): $$\boxed{n-1\ \text{comparisons.}}$$
(c) Reverse-sorted list. The $i$-th new element (for $i=2,\dots,n$) must be compared against and shifted past ALL $i-1$ elements already placed before it stops (every prior element is larger): $$\sum_{i=2}^n(i-1) = \sum_{k=1}^{n-1}k = \frac{(n-1)n}{2} = \boxed{\frac{n(n-1)}{2}\ \text{comparisons.}}$$
(d) Worst-case complexity. $\frac{n(n-1)}{2}=\frac12n^2-\frac12n$ is dominated by its $n^2$ term: $$\boxed{O(n^2).}$$

Final results — Question 10
Part	Result
(a)	Grows a sorted prefix by inserting each new element into place
(b) Best case	$n-1$ comparisons
(c) Worst case	$n(n-1)/2$ comparisons
(d)	$O(n^2)$

Topic: Insertion sort — algorithm mechanics and best/worst-case comparison counting.

Key relations: Best case (already sorted): $\Theta(n)$ comparisons; worst case (reverse sorted): $\Theta(n^2)$ comparisons, exactly $\binom n2=\frac{n(n-1)}2$; both cases share the same $O(n^2)$ worst-case classification since Big-O describes an upper bound on the ALGORITHM, not one particular input.

Why this works: Each new element's comparison count equals the number of already-placed elements it must "pass" before finding its spot — zero extra passes when the list is already ordered (every element stops after one check), but the maximum $i-1$ passes when the list is in the exact opposite order (every prior element must be shifted).

Common pitfall: Reporting $n(n-1)/2$ as the answer for the ALREADY-sorted case (that's the worst case); forgetting that Big-O worst-case complexity is stated as a bound over ALL inputs of size $n$, not just the reverse-sorted one.

Source: Rosen, Discrete Mathematics and Its Applications, §3.1 (algorithms), §3.3 (complexity of algorithms — sorting).

← Question 9 Next: Question 11 →