Week 3 - Searching, Lower Bounds, Invariants, Elementary Sorting & Mergesort

Sources & coverage

• Lecture 4 (Püschel): searching (linear and binary search), the first lower-bound proofs, the sorting problem, the sortedness check, Bubble Sort, invariants, Selection Sort.
• Lecture 5 (Püschel): Insertion Sort, Mergesort (including Merge), analysis.
• Script Suchen und Sortieren (version of 7 Oct 2026): Kap. 1 and §§2.1–2.4 cover this week. §§2.5–2.7 (Quicksort, Heapsort, lower bound for sorting, Bucketsort) were not covered in lecture yet. They are announced for next week and are left out here.
• These notes follow the script’s numbering (Def. 1.1, Def. 2.1, §1.2.1, …). Where the lecture and script differ in pseudocode, examples or details, this is marked ⚠ Discrepancy.

Correction to the Week 2 notes (Maximum Subarray Sum)

In the recap at the start of Lecture 4, Püschel says that both divide and conquer and an inductive approach worked for Maximum Subarray Sum, and that the final algorithm was $O(n)$. He later adds (end of Lecture 4) that this inductive algorithm assumed “the problem is already solved up to position $j$” and extended the solution by one step, so it was implicitly based on an invariant. The Week 2 recording was missing this part, so the Week 2 notes stopped at the $O(n\log n)$ divide-and-conquer reconstruction. A reconstruction of the linear algorithm is in §5.1 below. ⚠ Reconstruction: check it against the handwritten notes.

---

1. Executive Overview & Core Objectives

Searching (Suchen) in an unsorted array costs $\Theta (n)$ comparisons, and this is optimal. In a sorted array, binary search (binäre Suche) needs only $\Theta (\log n)$ comparisons, and this too is optimal. Both optimality claims are lower bounds (untere Schranken): statements about every possible comparison-based algorithm. The second one is proved with a decision tree (Entscheidungsbaum), an information-theoretic argument. Since sorting makes searching dramatically faster, we turn to sorting (Sortieren). Bubble Sort, Selection Sort and Insertion Sort all still cost $\Theta (n^2)$ operations, but they illustrate the central new concept: the (loop) invariant (Invariante). An invariant can be used to prove correctness by induction, and, the other way round, to design an algorithm. Mergesort (divide and conquer) is the first $\Theta (n\log n)$ sorting algorithm, at the price of $O(n)$ extra memory: it is not in place.

Learning objectives. After this week you should be able to:

• State the search problem (Def. 1.1) and the sorting problem (Def. 2.1) formally, together with their elementary operations.
• Write linear search and binary search (recursive and iterative), and analyse them ($\Theta (n)$ and $\Theta (\log n)$).
• Explain why lower bounds are hard (they cover all algorithms), and reproduce:
  • the $\Omega (n)$ bound for unsorted search (“every element must take part in a comparison”),
  • the $\Omega (\log n)$ decision-tree bound for sorted search.
• Use binary search to find the insertion position (Einsortierung) of an element that is not in the array.
• Define and use a loop invariant: initialisation, maintenance (induction step), termination.
• Derive Selection Sort and Insertion Sort from an invariant.
• Count comparisons and swaps/moves for Bubble, Selection and Insertion Sort in the worst case.
• Write Mergesort and Merge, trace the recursion order, and solve $T(n)=2T(n/2)+dn$ to get $\Theta (n\log n)$.
• Explain “in place” and why Mergesort is not.

---

2. Core Concepts & Formal Definitions

2.1 Searching (Script Kap. 1)

Definition 1.1 (Search / Suche)

Given: an array $A[\mathrm{1..}n]$ of numbers and an element $b$.
Find: an index $k$ with $A[k]=b$, or the answer “nicht gefunden” (not found) if $b$ does not occur in $A$.
Elementary operation: comparisons (Vergleiche) such as $<,>,=$. We study only comparison-based search. Other kinds (e.g. hash tables) come later.

Remarks:

• Restricting to numbers is no loss of generality: every object in a computer is a bit string, which can be read as a number.
• Motivation: find the exam of one student, given the student number (Matrikelnummer), in a stack of 600–1000 exams. Whether the stack is sorted makes a huge difference. We distinguish
  • Case 1: $A$ unsorted (§1.1),
  • Case 2: $A$ sorted ascending, $A[1]\le A[2]\le \cdots \le A[n]$ (§1.2).

Definition (Pseudocode), clarified in Lecture 4

Pseudocode is not a defined programming language. Whether you write for or “für”, use $i$ or $j$, or mix in plain text is irrelevant. The only goal is that the reader understands the algorithm. The script adds that its level of detail may depend on the audience; e.g. “index of the maximum” need not be spelled out.

2.2 Lower bounds and $\Omega$

Definition (Lower bound / untere Schranke)

A lower bound for a problem says that every algorithm (in a fixed model, here: comparison-based) needs at least a certain number of elementary operations in the worst case.

Definition ( $\Omega$, from the exercise sheet)

For $f,g:\mathcal{N}\to {\mathbb{R}}^{+}$:
$f\in \Omega (g):⟺g\in O(f)⟺\exists c>0\forall n\in \mathcal{N}:f(n)\ge c\cdot g(n).$
$\Omega$ expresses “grows at least as fast as”, i.e. an asymptotic lower bound. Moreover $\Theta (g)=O(g)\cap \Omega (g)$.

Exam Trap: lower bounds are about all algorithms

“Linear search must look at every element” is not a lower-bound proof. It talks about one specific algorithm. Püschel’s counter-thought: some unknown algorithm might first impose partial structure on the array cheaply (say in ${\log }^{5}n$ steps) and then need fewer comparisons. A valid lower-bound argument must also cover algorithms nobody has thought of yet. That is why lower bounds are hard, and why for many problems it is unknown whether the best known algorithm is optimal.

2.3 Trees: terminology needed this week

Definition (Binary tree terminology)

• A tree (Baum) consists of nodes (Knoten) connected by edges (Kanten). In a binary tree (Binärbaum) each node has at most two children (Nachfolger).
• The top node is the root (Wurzel). Nodes without children are leaves (Blätter).
• Depth (Tiefe) of a node = number of edges on the path from the root; the root has depth 0.
• Height (Höhe) $h$ of the tree = maximum depth of a leaf. The script uses “height” and “depth” of the tree interchangeably.

Definition (Decision tree / Entscheidungsbaum, "Suchbaum" in the lecture)

Any comparison-based algorithm, for a fixed input size $n$, can be drawn as a binary tree:

• each inner node is a comparison (any comparison, even something like ”$A[7]<A[3]+A[12]$?”);
• its two children are the continuations for the answers yes / no;
• each leaf is a return (an output).

Running the algorithm on an input = following one root-to-leaf path. The number of comparisons in the worst case = the height $h$ of the tree.

⚠ Terminology: in the lecture Püschel calls this a “Suchbaum” (search tree). The script calls it an Entscheidungsbaum (decision tree). “Binary search tree” will later mean a data structure, so prefer “decision tree” here.

2.4 Sorting (Script Kap. 2)

Definition 2.1 (Sorting / Sortieren)

Given: an array $A[\mathrm{1..}n]$ of numbers.
Find: a permutation (Umordnung, Permutation) $A^{\prime }$ of $A$ that is sorted ascending:
$\forall 1\le i<j\le n:A^{\prime }[i]\le A^{\prime }[j].$
Elementary operations: comparisons, and swaps (Vertauschungen) of two array elements, more generally moves (Bewegungen), i.e. writes.

Definition (In place)

A sorting algorithm works in place if it computes $A^{\prime }$ inside the memory of $A$, using only $O(1)$ extra memory (a constant number of helper variables). Motivation: sorting 100 GB of data with another 100 GB of scratch space is undesirable. When extra memory spills to slower storage (disk instead of RAM), the algorithm can slow down drastically.

Why sort? Sorting makes search much faster ($\log n$ instead of $n$). Sort once, then do many $O(\log n)$ searches. The one-time sorting cost amortises (amortisiert sich). Example: student records, keyed by student number, are sorted once and then looked up repeatedly.

2.5 Invariants

Definition (Loop invariant / Invariante)

An invariant $I(j)$ is a statement depending on the loop counter $j$ that holds after every iteration of a loop. “Invariant” means “unchanging”: the statement form stays the same while $j$ changes.
A correctness proof with an invariant has three parts:

1. Initialisation: $I$ holds before the first iteration (e.g. $I(0)$ or $I(1)$). This is the induction base.
2. Maintenance: if $I(j)$ holds and one iteration runs, then $I(j+1)$ holds. This is the induction step.
3. Termination: the invariant at the end (e.g. $I(n-1)$ or $I(n)$) implies that the output is correct.

Intuition: invariant = induction applied to a loop

The invariant describes a partially solved state: “the problem is solved up to stage $j$”. The loop body is the step $j\to j+1$. This is the same pattern as week 1’s inductive algorithms (star search) and the inductive $O(n)$ Maximum Subarray algorithm. Püschel: the concept is identical to the invariants you meet in the parallel programming course (“Einführung in die Programmierung”). Formal verification is its own field; here invariants are used for correctness arguments and, especially, for design.

Definition (Inductive algorithm / induktiver Algorithmus)

An algorithm that builds the solution step by step, making progress by one unit per step (from the solution for stage $j$ to the solution for stage $j+1$). Selection Sort and Insertion Sort are inductive. Each is naturally described by an invariant.

---

3. Step-by-Step Derivations & Mathematical Proofs

3.1 Linear search (Script §1.1)

Linear-Search(A[1..n], b)
    for i := 1 to n:
        if A[i] = b: return i
    return "nicht gefunden"

Runtime. In the worst case ($b$ not present, or at the last position) the loop runs $n$ times, with one comparison each. “Loops become sums”:
${\sum }_{i=1}^{n}1=n⟹\Theta (n)\text{ comparisons (exactly }n\text{ in the worst case)}.$

3.2 Lower bound for unsorted search: $\Omega (n)$

Claim

Every comparison-based algorithm for searching an unsorted array needs $\Omega (n)$ comparisons in the worst case.

Lecture argument.

1. Every one of the $n$ array elements must take part in at least one comparison. Suppose some element $A[i]$ is never compared. Then the algorithm behaves identically whether $A[i]=b$ or not, so for one of the two cases its answer is wrong. This also covers clever algorithms that first impose some structure: imposing structure needs comparisons too, so the argument still applies.
2. Each comparison involves two “elements” (array entries or $b$). In total $n+1$ items ($A[\mathrm{1..}n]$ and $b$) must each appear in a comparison. So
   $\#\text{comparisons}\ge \frac{n+1}{2}\in \Omega (n).$

Püschel adds that in fact exactly $n$ comparisons are necessary, so linear search is exactly optimal. But this needs a more careful argument than the one above.

⚠ Lecture vs. script: the script argues differently and more directly. Suppose $b\notin A$. After the algorithm has read $n-1$ elements, it cannot yet decide, because $b$ could be in the last unread element. So it must read all $n$. This is the intuition behind the sharper bound of $n$. The lecture’s $(n+1)/2$ argument is weaker but fully rigorous for $\Omega (n)$.

3.3 Binary search (Script §1.2)

Idea (common sense, used by anyone sorting a stack of exams): look at the middle. If it is not the target, the comparison tells you which half the target must be in; throw the other half away and repeat. This is divide and conquer: only one of the two halves is ever searched.

Middle index.
$m=\lfloor \frac{n+1}{2}\rfloor (\lfloor \cdot \rfloor =\text{floor, round down}).$
Examples: $n=3\Rightarrow m=\lfloor 2\rfloor =2$ (the exact middle). $n=4\Rightarrow m=\lfloor 2.5\rfloor =2$.

Why $\lfloor (n+1)/2\rfloor$ and not $\lfloor n/2\rfloor$? (student question)

For $n=3$, $\lfloor 3/2\rfloor =1$ is not the middle. Asymptotically it makes no difference. Equivalently one can use $\lceil n/2\rceil$, since $\lceil n/2\rceil =\lfloor (n+1)/2\rfloor$ for every integer $n$.

Recursive version (lecture), corrected:

Binary-Search(A[1..n], b)              // n = current length of the array
    if n = 0: return "nicht gefunden"   // empty array
    m := floor((n+1)/2)
    if A[m] = b: return m               // lucky case
    if b < A[m]:
        return Binary-Search(A[1..m-1], b)          // left half
    else:
        r := Binary-Search(A[m+1..n], b)            // right half
        if r = "nicht gefunden": return r
        return m + r                    // translate index back (offset m)

⚠ Discrepancies / corrections in the lecture version:

1. Püschel first wrote the right-half call as A[1..m+1]. A student caught it (“klassisch idiotischer Fehler”). It must be A[m+1..n].
2. The transcript has “Return N” in the lucky case. It must be return m.
3. $n$ inside the routine means the length of the current (sub)array, not the original $n$ (clarified after a student question).
4. A recursive call on A[m+1..n] returns an index relative to that subarray. In a real implementation you must add the offset $m$ (or pass the bounds $\ell ,r$ as parameters). Püschel called this a programming detail that doesn’t change the idea. The extra line return m + r above handles it.

Iterative version (script), with invariant ”$A[\ell ..r]$ is the remaining search range”:

Binary-Search(A[1..n], b)
    l := 1; r := n                      // initial search range
    while l <= r:
        m := floor((l + r) / 2)
        if A[m] = b: return m           // found
        else if A[m] > b: r := m - 1    // continue left
        else: l := m + 1                // continue right
    return "nicht gefunden"

Correctness (script). Since $A$ is sorted ascending: if $b<A[m]$, then positions $m,\dots ,n$ hold only keys $\ge A[m]>b$, so it suffices to search $1,\dots ,m-1$. The case $b>A[m]$ is symmetric. Termination: the search range shrinks by at least one element per step, so the procedure ends after finitely many steps.

3.4 Runtime of binary search: $O(\log n)$

After one step, at most $n/2$ positions remain (in both the “left” and the “right” case). The runtime is monotone in $n$ (a longer array never takes less time; script footnote: provable by induction). So for $n=2^k$:

$$T(n)\le \{\begin{array}{ll}c& n=1,\\ T(n/2)+d& n\ge 2,\end{array}\text{\hspace{1em}(1)}$$

where $c,d$ are constants. $d$ covers the work outside the recursive call: computing $m$, the two comparisons, and so on. It does not matter whether this is 1, 2 or 5 operations.

Why is "constant $d$" allowed? (lecture)

You only see at the end, after solving the recurrence, that the exact constant is irrelevant. It ends up as a factor in $d{\log }_{2}n$, which O-notation absorbs.

Telescoping (to guess):
$T(n)\le T(n/2)+d\le T(n/4)+2d\le T(n/8)+3d\le \cdots \le T(n/2^k)+kd=c+d{\log }_{2}n.$

Proof by induction (script) that $T(n)\le d{\log }_{2}n+c$ for all $n=2^k$, $k\ge 0$:

• Base ($k=0$, $n=1$): $T(1)\le c=d{\log }_{2}1+c$. ✓
• Step ($k\to k+1$, $n=2^{k+1}$):

$$\begin{array}{rlrl}T(n)& \le T(n/2)+d& & \text{by (1)}\\ & =T(2^k)+d& & \\ & \le d{\log }_2(2^k)+c+d& & \text{IH for }{2}^k\\ & =d(k+1)+c=d{\log }_{2}n+c.✓& & \end{array}$$

So $T(n)\le O(\log n)$. If $n$ is not a power of two, the result is the same; nothing interesting is added.

How fast is $\log n$?

${\log }_2(10^6)\approx 20$: searching a million sorted elements takes about 20 steps. ${\log }_2(10^{12})\approx 40$: a million times a million takes about 40 steps. Püschel: on a planet where search were more expensive, our digital world would not work as well.

3.5 Lower bound for sorted search: $\Omega (\log n)$ (Script §1.2.1)

Theorem

Every comparison-based search algorithm on a sorted array of length $n$ needs, in the worst case, at least ${\log }_2(n+1)\in \Omega (\log n)$ comparisons. Binary search is therefore asymptotically optimal.

Proof idea: draw an arbitrary comparison-based algorithm as a decision tree, then count.

Example: decision tree of binary search for $n=3$ (lecture). Only element comparisons are counted; index arithmetic such as computing $m$ is left out.

                    [ A[2] = b ? ]
                   yes /      \ no
              return 2      [ b < A[2] ? ]
                           yes /       \ no
                   [ b = A[1] ? ]     [ b = A[3] ? ]
                   yes /   \ no       yes /   \ no
              return 1    NG       return 3    NG

(NG = nicht gefunden.) Worst case: 3 comparisons = height of this tree.

General argument. Take any comparison-based algorithm and its decision tree, with height $h$.

1. Worst-case comparisons $=h$. Each input $b$ produces one root-to-leaf path. The longest path has $h$ comparisons.
2. Number of possible outputs $=n+1$: the $n$ indices $1,\dots ,n$, plus “nicht gefunden”. Each output needs at least one leaf, so
   $\#\text{leaves}\ge n+1.$
3. A binary tree of height $h$ has at most $2^h$ leaves. Depth 1 gives at most 2 leaves, depth 2 at most 4, depth 3 at most 8, and in general each level at most doubles.
4. Combining:
   $n+1\le \#\text{leaves}\le 2^h⟹h\ge {\log }_2(n+1)\in \Omega (\log n).■$

⚠ Transcript garble: the final line was transcribed as ”$H$ kleiner gleich ${\log }_2(n+1)$ größer gleich”. The correct conclusion is $h\ge {\log }_2(n+1)$.

⚠ Lecture vs. script: the script counts nodes instead of leaves. A binary tree of height $h$ has at most $2^0+2^1+\cdots +2^h=2^{h+1}-1<2^{h+1}$ nodes, and there are at least $n+1$ nodes, so
$n+1\le \#\text{nodes}<2^{h+1}⟹h>{\log }_2(n+1)-1=\Omega (\log n).$
This is slightly weaker. Its footnote notes that counting leaves directly (as in the lecture) gives the sharper $h\ge {\log }_2(n+1)$. Counting nodes is useful when, as in the script’s Fig. 1.1, a return can follow directly after a yes-answer at an inner level.

Information-theoretic view (script)

A comparison yields one bit of information. With $h$ comparisons, an algorithm can distinguish at most $2^h$ situations. Distinguishing $n+1$ outcomes needs $h\ge {\log }_2(n+1)$. This generalises to the concept of entropy.

Exam Trap: the bound only holds for comparison-based algorithms

A student asked whether this rules out faster search. It does not rule out non-comparison methods such as hash tables. The argument needs every branching to be binary (yes/no). Püschel: “If you want to consider something else, keep studying.”

3.6 Insertion position via binary search (Script §1.2.2, Einsortierung)

Often we want to know where $b$ would have to be inserted to keep the array sorted. Binary search gives this as a side effect: it ends exactly where $b$ “would have been”.

Iterative version: if $b$ is not found, then at termination
$\ell =r+1\text{and}A[r]<b<A[\ell ],$
so the insertion position is $\ell$.

Why $\ell =r+1$ (script footnote): we left the loop, so $\ell >r$. One checks that $\ell$ is never set beyond $r+1$ and $r$ never below $\ell -1$. If $b$ occurs multiple times, there are several valid answers.

3.7 Checking sortedness (Script, start of Kap. 2)

Sorted(A[1..n])
    for i := 1 to n-1:
        if A[i] > A[i+1]: return false     // sortedness violated
    return true

$n-1$ iterations with one comparison each give $\Theta (n)$. This is optimal: the check must look at every element.

3.8 Bubble Sort (Script §2.1)

Idea: modify the sortedness check. Whenever $A[i]>A[i+1]$ (a violation), repair it by swapping.

One pass alone does not sort. Lecture example $A=(3,7,5,1,4)$, one pass:
$(3,7,5,1,4)\to (3,5,7,1,4)\to (3,5,1,7,4)\to (3,5,1,4,7).$
Not sorted. But the largest element (7) is now at its correct place: once the largest element is reached, it wins every comparison and is swapped all the way to the right. It “bubbles up”, hence the name.

Fix: repeat the pass.

Bubble-Sort(A[1..n])
    for j := 1 to n-1:              // passes  (script: j = 1..n)
        for i := 1 to n-1:          // optimisation: i = 1..n-j suffices
            if A[i] > A[i+1]:
                swap A[i] and A[i+1]

Full lecture trace on $(3,7,5,1,4)$:

Pass	Steps	Result
$j=1$	swap 7,5; swap 7,1; swap 7,4	$(3,5,1,4,7)$
$j=2$	3,5 ok; swap 5,1; swap 5,4; 5,7 ok	$(3,1,4,5,7)$
$j=3$	swap 3,1; rest ok	$(1,3,4,5,7)$
$j=4$	nothing to do (by chance)	$(1,3,4,5,7)$

Optimisation (student remark). After pass $j$ the $j$ largest elements are in place, so the comparisons at the end are useless. The inner loop may run only up to $n-j$. This does not change the asymptotics.

⚠ Lecture vs. script: the lecture’s outer loop runs $j=\mathrm{1..}n-1$; the script’s runs $j=\mathrm{1..}n$, and a footnote notes that $n-1$ passes suffice. The script uses the example $(5,3,7,1,4)$, sorted after 3 passes.

Runtime.

• Comparisons: two nested loops become two nested sums:
  ${\sum }_{j=1}^{n-1}{\sum }_{i=1}^{n-1}1=(n-1{)}^2=\Theta (n^2).$
  With the $n-j$ optimisation: ${\sum }_{j=1}^{n-1}(n-j)=\frac{n(n-1)}{2}$, still $\Theta (n^2)$.
• Swaps: at most one per comparison, so $O(n^2)$. This is tight in the worst case: the reversed array $[n,n-1,\dots ,1]$ needs $\Theta (n^2)$ swaps (script).

Beyond the lecture: exact swap count

Every adjacent swap of an out-of-order pair removes exactly one inversion (a pair $i<j$ with $A[i]>A[j]$). So Bubble Sort makes exactly as many swaps as the input has inversions, at most $\left(\genfrac{}{}{0ex}{}{n}{2}\right)=\frac{n(n-1)}{2}$, attained by the reversed array.

Correctness via invariant (lecture and script):

$I(j)$: After $j$ passes of the outer loop, the $j$ largest elements are at their correct (final) positions.

Formally (script): $A[n-j+1]\le A[n-j+2]\le \cdots \le A[n]$, and every element left of position $n-j+1$ is $\le A[n-j+1]$.

• Initialisation: $I(0)$ is trivial (“the 0 largest elements are in place”).
• Maintenance $I(j)\Rightarrow I(j+1)$: the $j$ largest elements sit at the end, and nothing to their left is larger. So the test A[i] > A[i+1] never moves them, and no swaps happen for $i=n-j,\dots ,n-1$. Meanwhile, the largest element of the remaining part $A[\mathrm{1..}n-j]$, i.e. the $(j+1)$-largest overall, bubbles to position $n-j$ during pass $j+1$.
• Termination: $I(n-1)$ says the $n-1$ largest elements are in place. Then the single remaining element must also be in place, so the array is sorted.

⚠ Script detail: the script writes the second condition with strict "$A[i]<A[n-j+1]$". With duplicate values this is false in general. It must be "$\le$".

3.9 Selection Sort (Script §2.2): from invariant to algorithm

The key insight of this lecture: instead of starting from an algorithm and finding its invariant, start with an invariant and design the algorithm that maintains it. This works especially well for inductive algorithms.

Take the same invariant as Bubble Sort:

$I(j)$: the last $j$ positions $A[n-j+\mathrm{1..}n]$ contain the $j$ largest elements, sorted, at their final positions.

   A:  [   first n-j: unsorted rest    |  last j: sorted & final ]
       1                          n-j    n-j+1                  n

• At the start, $I(0)$ holds (the final part is empty).
• If we can get from $I(j)$ to $I(j+1)$, we eventually reach $I(n-1)$, which means sorted.

Progress by one ($I(j)\to I(j+1)$): the final part is perfect; nothing there may change. Which element must go to position $n-j$? The maximum of the unsorted part $A[\mathrm{1..}n-j]$. Find it and swap it into position $n-j$. This is Selection Sort.

Selection-Sort(A[1..n])                 // lecture version
    for j := 0 to n-2:
        k := index of the maximum of A[1..n-j]
        swap A[k] and A[n-j]

⚠ Lecture vs. script: the script writes for j := n downto 1: k := index of max in A[1..j]; swap A[k], A[j]. This is the same algorithm with the script’s $j$ equal to the lecture’s $n-j$. The script’s last iteration ($j=1$) is trivial.

Lecture trace on $(3,7,5,1,4)$; ”|” marks where the invariant region begins:

Invariant before	Array	Max of unsorted part	After swap
$I(0)$	$(3,7,5,1,4)$	7	$(3,4,5,1\mid 7)$
$I(1)$	$(3,4,5,1\mid 7)$	5	$(3,4,1\mid 5,7)$
$I(2)$	$(3,4,1\mid 5,7)$	4	$(3,1\mid 4,5,7)$
$I(3)$	$(3,1\mid 4,5,7)$	3	$(1\mid 3,4,5,7)$
$I(4)$	sorted	–	$(1,3,4,5,7)$

Starting from the invariant gives the correctness proof for free. Initialisation is trivial, each iteration establishes the next invariant by construction, and $I(n-1)$ implies sortedness.

Finding the maximum (student question): the maximum of $m$ elements needs exactly $m-1$ comparisons. Assume the first element is the maximum, scan the rest, and update whenever something larger appears.

Runtime.

• Swaps: $n-1$ iterations, one swap each, so $O(n)$. This is a big improvement over Bubble Sort’s $O(n^2)$.
• Comparisons: iteration $j$ finds the maximum of $n-j$ elements with $n-j-1$ comparisons:
  ${\sum }_{j=0}^{n-2}(n-j-1)=(n-1)+(n-2)+\cdots +1=\frac{n(n-1)}{2}=\Theta (n^2).$
  (Tip from the lecture: when a sum like $\sum (n-j-1)$ looks unfriendly, write it out: $j=0$ gives $n-1$, $j=1$ gives $n-2$, …, $j=n-2$ gives $1$.)

Summary: $\Theta (n^2)$ comparisons, $O(n)$ swaps, in place.

3.10 Insertion Sort (Script §2.3): a different invariant

Try a different invariant, this time at the front:

$I(j)$: the first $j$ elements $A[\mathrm{1..}j]$ are sorted, but not necessarily at their final positions (they need not be the $j$ smallest elements).

   A:  [ first j: sorted (not final) |   rest: untouched   ]
       1                          j    j+1                n

• Initialisation: $I(1)$ holds, since a single element is sorted by itself.
• Termination: $I(n)$ means all $n$ elements are sorted, hence correct.
• Maintenance $I(j)\to I(j+1)$ (student proposal): take the next element $A[j+1]$ and insert it at the right place in the sorted prefix $A[\mathrm{1..}j]$, shifting larger elements one step right.

Lecture example: prefix $(1,2,4,7,10)$, next element $5$:
$(1,2,4,7,10\mid 5,27,\dots )\to (1,2,4,5,7,10\mid 27,\dots ).$
Now the first 6 elements are sorted.

Finding the position cheaply. The prefix is sorted, so use binary search ($O(\log j)$) instead of a linear scan ($O(j)$). Binary search returns the insertion position $k$ as a side effect (§3.6).

Insertion-Sort(A[1..n])                 // lecture version, corrected
    for j := 1 to n-1:
        k := insertion position of A[j+1] in A[1..j]   // binary search
        x := A[j+1]                     // remember it: shifting overwrites A[j+1]
        shift A[k..j] to A[k+1..j+1]
        A[k] := x

⚠ Discrepancies:

1. Püschel said “this time from 1 to $n$” for the loop, but the body inserts $A[j+1]$, and his own analysis sums $j=\mathrm{1..}n-1$. The loop must run $j=\mathrm{1..}n-1$.
2. The script indexes differently: for j := 2 to n, inserting $A[j]$ into $A[\mathrm{1..}j-1]$, with $k$ := smallest index in $\{\mathrm{1..}j-1\}$ with $A[j]\le A[k]$. Edge case: if $A[j]$ is larger than everything in the prefix, no such index exists, and $A[j]$ simply stays at position $j$ (no shift).

Lecture trace on $(3,7,5,4,1)$:

Invariant	Insert	Result
$I(1)$: $(3)$	7 goes after 3	$(3,7\mid 5,4,1)$
$I(2)$	5 between 3 and 7	$(3,5,7\mid 4,1)$
$I(3)$	4 between 3 and 5; shift 5, 7	$(3,4,5,7\mid 1)$
$I(4)$	1 at the front; shift 4 elements (worst case)	$(1,3,4,5,7)$
$I(5)$	–	sorted

Runtime.

• Comparisons: binary search on $j$ elements costs $O({\log }_{2}j)$. Sum over iterations, then use that a sum of logs is the log of the product (school mathematics, middle-of-the-night knowledge):
  ${\sum }_{j=1}^{n-1}{\log }_{2}j={\log }_2\left({\prod }_{j=1}^{n-1}j\right)={\log }_2((n-1)!)\le {\log }_2(n!)\le O(n\log n).$
  ($\log (n!)=\Theta (n\log n)$ was on exercise sheet 2. The upper bound is immediate from $n!\le n^n$.)
• Moves: in the worst case (new element goes to the front, e.g. a reversed array) we shift $j$ elements and write $x$, so $j+1$ moves:
  ${\sum }_{j=1}^{n-1}(j+1)\le O(n^2).$

Summary: $O(n\log n)$ comparisons (the first time we see this!) but $O(n^2)$ moves. Both bounds are tight in the worst case (script). In place. Overall still quadratic.

Different invariant, different trade-off

• Selection Sort (invariant at the back, final positions): few swaps, many comparisons.
• Insertion Sort (invariant at the front, only sorted): few comparisons, many moves.

Both are still $\Theta (n^2)$ overall. To beat that, we need a different design principle.

3.11 Mergesort (Script §2.4): divide and conquer

Idea (“probably the most natural-looking”):

1. Divide: split the array in the middle.
2. Conquer: sort the left half and the right half recursively.
3. Combine: merge (verschmelzen) the two sorted halves into one sorted array.

Mergesort(A, l, r)                      // sorts A[l..r]; initial call: l = 1, r = n
    if l < r:                           // at least 2 elements
        m := floor((l + r) / 2)
        Mergesort(A, l, m)              // sort left half
        Mergesort(A, m+1, r)            // sort right half
        Merge(A, l, m, r)               // merge both halves

All recursive calls only split. All the actual work happens in Merge.

Merge, key observation: the first (smallest) element of the result is either the first element of the left half or the first element of the right half, because both halves are sorted. Keep two pointers $i$ (left) and $j$ (right). Compare $A[i]$ and $A[j]$, write the smaller one to the output, and advance that pointer.

Example (lecture): merge $(1,4,7,9)$ and $(2,3,5,8)$:

• 1 vs 2: take 1. 4 vs 2: take 2. 4 vs 3: take 3. 4 vs 5: take 4. 7 vs 5: take 5. 7 vs 8: take 7. 9 vs 8: take 8. Left rest: 9.
• Result: $(1,2,3,4,5,7,8,9)$.

Merge(A, l, m, r)                       // A[l..m] and A[m+1..r] are sorted
    B := new array (extra memory, same size as A[l..r])
    i := l          // first unused element, left half
    j := m + 1      // first unused element, right half
    k := l          // next position in B (script: k := 1, B indexed from 1)
    while i <= m and j <= r:            // neither half exhausted
        if A[i] < A[j]:
            B[k] := A[i]; i := i + 1; k := k + 1
        else:
            B[k] := A[j]; j := j + 1; k := k + 1
    copy the remaining elements of the left OR right half to B   // only one has a rest
    copy B back to A[l..r]

Why the “rest” step: when one pointer runs past its half, the other half may still hold elements. They are all larger than everything written so far and already sorted, so they are appended unchanged. Why copy back: Mergesort works on $A$. Alternatively one could continue working with $B$.

Example: recursion order (lecture), $A=(9,4,7,1,2,5,3,8)$

First call: $l=1$, $r=8$, $m=\lfloor 9/2\rfloor =4$. The recursion always finishes the left part completely before touching the right part. The merges happen in this order:

1. $(9)+(4)\to (4,9)$
2. $(7)+(1)\to (1,7)$
3. $(4,9)+(1,7)\to (1,4,7,9)$
4. $(2)+(5)\to (2,5)$
5. $(3)+(8)\to (3,8)$
6. $(2,5)+(3,8)\to (2,3,5,8)$
7. $(1,4,7,9)+(2,3,5,8)\to (1,2,3,4,5,7,8,9)$

Calls on single elements ($l=r$) do nothing. Püschel: the processing order of recursive algorithms is not always obvious, so trace it once by hand.

Correctness (script) by strong induction on the length $r-l+1$:

• Base: $l=r$, a single element, already sorted.
• Step: let $l<r$. Then $m<r$ and $m+1>l$, so both recursive ranges are strictly shorter than $r-l+1$. By the induction hypothesis both halves are sorted correctly. If Merge correctly combines two sorted ranges, the result is correct.
• Merge correctness: induction on $k$. The invariant is: the output so far contains the smallest elements of $A[l..r]$ in sorted order, and the remaining elements are exactly $A[i..m]$ and $A[j..r]$.

⚠ Script detail: the script states the Merge invariant as ”$B[\mathrm{1..}k]$ contains the $k$ smallest elements”. Since $k$ is the next free position, it should be $B[\mathrm{1..}k-1]$ (the $k-1$ smallest). This is an off-by-one in the statement, not in the algorithm.

Runtime: recurrence. Let $n=2^k$, and let $T(n)$ count comparisons (or moves). Merge on $n$ elements costs at most $dn$: one linear pass, each element read once and written once (plus copying back).
$T(1)=c,T(n)\le 2T(n/2)+dn.$

Telescoping:

$$\begin{array}{rl}T(n)& \le 2T(n/2)+dn\\ & \le 2(2T(n/4)+dn/2)+dn=4T(n/4)+2dn\\ & \le 8T(n/8)+3dn\\ & ⋮\\ & \le 2^{k}T(1)+kdn=cn+dn{\log }_{2}n.\end{array}$$

Induction proof of $T(2^k)\le d{2}^{k}k+c{2}^k$:

• Base $k=0$: $T(1)=c$. ✓
• Step: $T(2^{k+1})\le 2(d{2}^{k}k+c{2}^k)+d{2}^{k+1}=d{2}^{k+1}(k+1)+c{2}^{k+1}$. ✓ $■$

So $T(n)\le dn{\log }_{2}n+cn\le O(n\log n)$, and in fact $\Theta (n\log n)$, for both comparisons and moves.

Alternative analysis by levels (script). The recursion has ${\log }_{2}n$ levels. On each level, every one of the $n$ numbers takes part in exactly one Merge. Each comparison places at least one number for good, so there are $\le n$ comparisons per level. There are exactly $2n$ copy operations per level (write to $B$, copy back). Total:
$\underset{\text{levels}}{\underbrace{{\log }_{2}n}}\cdot \underset{\text{comparisons per level}}{\underbrace{n}}\le O(n\log n).$

Extra memory: $B$ needs $O(n)$ cells. Mergesort is not in place. In-place merging fails because the two pointers advance irregularly: writing into $A$ directly would overwrite elements still needed. (The script notes that reducing Mergesort’s extra memory is possible but much more complicated.) Püschel ironically said “glücklicherweise” (fortunately) about the $O(n)$ extra space. It is of course a disadvantage: a billion extra cells for a billion numbers is expensive.

---

4. Worked Examples & Applications

Example: overview of the sorting algorithms so far (Script Table 2.1, restricted to what was covered)

Algorithm	Comparisons	Moves	Extra space	Design idea
Bubble Sort	$\Theta (n^2)$	$O(n^2)$	$O(1)$	repair violations of the sortedness check
Selection Sort	$\Theta (n^2)$	$O(n)$	$O(1)$	invariant at the back: select the max
Insertion Sort	$O(n\log n)$	$O(n^2)$	$O(1)$	invariant at the front: insert the next element
Mergesort	$\Theta (n\log n)$	$\Theta (n\log n)$	$O(n)$	divide and conquer, merge

Example: decision tree of binary search, $n=6$ (Script Fig. 1.1)

Root: $b=A[3]$? If yes, return 3. If no: $b<A[3]$?

• If yes: $b=A[1]$? If yes, return 1; otherwise return 2.
• If no: $b=A[5]$? If yes, return 5; otherwise $b<A[5]$? If yes, return 4; otherwise return 6.

Height 4, so at most 4 comparisons for 6 elements. (The figure omits explicit “not found” leaves for brevity.)

Exam Trap: index offsets in recursive binary search

Calling binary search on A[m+1..n] returns a position inside the subarray. Forgetting to add $m$ gives wrong indices. In the iterative version with $\ell ,r$ the problem does not arise.

Exam Trap: "Insertion Sort is $O(n\log n)$"

Only its comparisons are $O(n\log n)$ (with binary search). The shifts cost $\Theta (n^2)$ in the worst case, so the total runtime is $\Theta (n^2)$. Always state which operation you are counting.

Exam Trap: Selection Sort's swaps vs. comparisons

$O(n)$ swaps but $\Theta (n^2)$ comparisons: still quadratic. Even on an already sorted array, Selection Sort performs all $\frac{n(n-1)}{2}$ comparisons.

Exam Trap: invariant must imply correctness at the end

Insertion Sort’s invariant (“prefix sorted”) only implies correctness at $j=n$, when the prefix is the whole array. Bubble/Selection Sort’s invariant (“largest $j$ elements are final”) already implies correctness at $j=n-1$. Know which index you end at.

Exam Trap: floor in the middle index

Mergesort uses $m=\lfloor (l+r)/2\rfloor$. Both recursive ranges, $[l,m]$ and $[m+1,r]$, are non-empty and strictly shorter whenever $l<r$. This is exactly what the correctness induction needs. With $[l,m-1]$ and $[m,r]$ the recursion could fail to shrink (e.g. $l=1,r=2$ gives $m=1$, and the second call would be on $[1,2]$ again).

---

5. Intuition & Conceptual Bridges

5.1 Bridge back: inductive Maximum Subarray Sum (⚠ reconstruction)

Püschel’s recap says the inductive approach gave $O(n)$, built by “assuming the problem is solved up to here and making progress by one”, i.e. an invariant. The standard version:

Invariant after processing $a_1,\dots ,a_j$:

• $\text{best}$ = maximum subarray sum within $a_1..a_j$ (or 0),
• $\text{suffix}$ = maximum sum of a subarray ending at position $j$ (or 0).

MaxSubarrayInductive(a_1, ..., a_n)     // reconstruction
    best := 0; suffix := 0
    for j := 1 to n:
        suffix := max(0, suffix + a_j)   // best subarray ending at j (or empty)
        best   := max(best, suffix)
    return best

Step $j\to j+1$: the best subarray ending at $j+1$ either extends the best one ending at $j$, or is empty. Cost: $O(1)$ per step, so $\Theta (n)$ overall. This is the same “invariant → inductive algorithm” pattern as Selection and Insertion Sort.

5.2 Intuition

Intuition: binary search halves the uncertainty

Each comparison can at best halve the set of remaining candidate answers. With $n+1$ possible answers, about ${\log }_2(n+1)$ halvings are needed. Binary search actually achieves this halving, which is why it matches the lower bound.

Intuition: why Mergesort beats the quadratic algorithms

The $\Theta (n^2)$ algorithms make progress by one element per linear-time step. Mergesort does $\Theta (n)$ work per level, but there are only ${\log }_{2}n$ levels, because the problem halves each time. Halving shows up again: halving gives $\log$ levels, as with binary search and Karatsuba.

Intuition: Mergesort vs. Insertion Sort

Insertion Sort inserts one element into a sorted list, which costs up to $j$ moves. Merge combines two sorted lists of length $n/2$ at once in linear time. Merging in bulk is far cheaper than inserting one by one.

5.3 Connections

• Back: recurrences and telescoping (weeks 1–2); $T(n)=T(n/2)+d$ is like Karatsuba’s recurrence but with one subproblem; $T(n)=2T(n/2)+dn$ is the same recurrence as reconstructed for divide-and-conquer Maximum Subarray Sum. Exercise sheet 2’s $\log (n!)=\Theta (n\log n)$ is used for Insertion Sort. Induction (week 1) underlies invariants and Mergesort’s correctness.
• Forward (script §§2.5–2.7, next week):
  • Quicksort: divide and conquer “in reverse” (partition first, then recurse), in place, $O(n\log n)$ in good cases, $O(n^2)$ worst case.
  • Heapsort: Selection Sort with a heap to find the maximum in $O(\log n)$: $O(n\log n)$ and in place.
  • Lower bound for comparison-based sorting: $\Omega (n\log n)$, with the same decision-tree argument as §3.5 but with $n!$ leaves (one per permutation). So Mergesort is asymptotically optimal.
  • Bucketsort: non-comparison-based, $\Theta (n)$ for restricted inputs.

---

6. Summary & Self-Assessment Questions

Cheat Table

Topic	Key fact
Search (Def. 1.1)	find $k$ with $A[k]=b$ or “nicht gefunden”; elementary op = comparison
Linear search	$\Theta (n)$; optimal (exactly $n$ comparisons needed)
Unsorted lower bound	every element in some comparison, 2 items per comparison: $\ge (n+1)/2\in \Omega (n)$
Binary search	$m=\lfloor (n+1)/2\rfloor$; $T(n)\le T(n/2)+d$, so $T(n)\le d{\log }_{2}n+c=O(\log n)$
Sorted lower bound	$n+1$ outputs, $\le 2^h$ leaves, so $h\ge {\log }_2(n+1)\in \Omega (\log n)$
Insertion position	iterative binary search ends with $\ell =r+1$, $A[r]<b<A[\ell ]$; insert at $\ell$
$\Omega$	$f\in \Omega (g)⟺g\in O(f)$; $\Theta =O\cap \Omega$
Sorting (Def. 2.1)	permutation with $A^{\prime }[i]\le A^{\prime }[j]$ for $i<j$; ops: comparisons, swaps/moves
In place	$O(1)$ extra memory
Sortedness check	$\Theta (n)$, optimal
Invariant proof	initialisation, maintenance (induction step), termination implies correctness
Bubble Sort	invariant: $j$ largest at the end; $\Theta (n^2)$ comparisons, $O(n^2)$ swaps
Selection Sort	same invariant, swap the max into place; $\Theta (n^2)$ comparisons, $O(n)$ swaps
Insertion Sort	invariant: prefix sorted; binary search gives $O(n\log n)$ comparisons; shifts $O(n^2)$
$\sum \log j$	${\sum }_{j=1}^{n-1}\log j=\log ((n-1)!)=\Theta (n\log n)$
Mergesort	$T(n)\le 2T(n/2)+dn$, so $dn{\log }_{2}n+cn=\Theta (n\log n)$; $O(n)$ extra space
Merge	two pointers, take the smaller, append the rest, copy back; $O(n)$

Self-Assessment Questions

Question 1. Run the iterative binary search (script version) on
$A=(2,5,8,12,16,23,38,56,72,91)$ for (a) $b=23$ and (b) $b=24$. List $\ell ,r,m$ in each step. For (b), give the insertion position and verify $A[r]<b<A[\ell ]$.

Solution to Question 1

(a) $b=23$:

• $\ell =1,r=10$: $m=\lfloor 11/2\rfloor =5$, $A[5]=16<23$, so $\ell =6$.
• $\ell =6,r=10$: $m=\lfloor 16/2\rfloor =8$, $A[8]=56>23$, so $r=7$.
• $\ell =6,r=7$: $m=\lfloor 13/2\rfloor =6$, $A[6]=23=b$. Return 6.

(b) $b=24$: the first two steps are identical ($\ell =6,r=7$).

• $m=6$: $A[6]=23<24$, so $\ell =7$.
• $\ell =7,r=7$: $m=7$, $A[7]=38>24$, so $r=6$.
• $\ell =7>r=6$: the loop ends, return “nicht gefunden”.

At termination $\ell =r+1=7$, and $A[r]=A[6]=23<24<38=A[7]=A[\ell ]$ ✓. Insertion position: 7. Four loop iterations ($\approx {\log }_{2}10\approx 3.3$, rounded up).

Question 2. Using the decision-tree argument, show that every comparison-based algorithm searching a sorted array of $n=1000$ elements needs at least 10 comparisons in the worst case. Why does the argument not apply to hash tables?

Solution to Question 2

The decision tree needs at least $n+1=1001$ leaves (indices $\mathrm{1..1000}$ plus “nicht gefunden”). A binary tree of height $h$ has at most $2^h$ leaves, so $2^h\ge 1001$, i.e. $h\ge {\log }_{2}1001\approx 9.97$. Since $h$ is an integer, $h\ge 10$. Worst-case comparisons $=h\ge 10$.
(Binary search achieves $\lceil {\log }_2(n+1)\rceil =10$ in the three-way comparison model, so it is optimal here.)
Hash tables: the argument assumes that every step branches in two ways (yes/no). A hash-table access computes an address from the key and jumps there directly. That is one step with up to $n$ possible outcomes, so the binary-tree counting no longer applies.

Question 3. Sort $A=(4,3,2,1)$ with (a) Bubble Sort (lecture version, inner loop $\mathrm{1..}n-1$, and also with the $n-j$ optimisation), (b) Selection Sort, (c) Insertion Sort. Count comparisons and swaps/shifts for each.

Solution to Question 3

(a) Bubble Sort:

• Pass 1: swap 4,3 to $(3,4,2,1)$; swap 4,2 to $(3,2,4,1)$; swap 4,1 to $(3,2,1,4)$. 3 swaps.
• Pass 2: swap 3,2 to $(2,3,1,4)$; swap 3,1 to $(2,1,3,4)$; 3,4 ok. 2 swaps.
• Pass 3: swap 2,1 to $(1,2,3,4)$; rest ok. 1 swap.

Comparisons: $3\cdot 3=9$ (with the optimisation: $3+2+1=6$). Swaps: 6 = number of inversions $=\left(\genfrac{}{}{0ex}{}{4}{2}\right)$, the worst case.

(b) Selection Sort:

• $j=0$: max of $(4,3,2,1)$ is 4 (3 comparisons); swap with $A[4]$, giving $(1,3,2,4)$.
• $j=1$: max of $(1,3,2)$ is 3 (2 comparisons); swap with $A[3]$, giving $(1,2,3,4)$.
• $j=2$: max of $(1,2)$ is 2 (1 comparison); swap with itself.

Comparisons: 6 $=\frac{4\cdot 3}{2}$. Swaps: 3 ($=n-1$, one of them trivial).

(c) Insertion Sort:

• Insert 3 into $(4)$: position 1, shift 1 element, giving $(3,4)$.
• Insert 2 into $(3,4)$: position 1, shift 2, giving $(2,3,4)$.
• Insert 1 into $(2,3,4)$: position 1, shift 3, giving $(1,2,3,4)$.

Shifts: $1+2+3=6$ (plus 3 writes of $x$, so $\sum (j+1)=9$ moves). Comparisons: one binary search per step on prefixes of length 1, 2, 3, i.e. $O(\log j)$ each.
The reversed array is the worst case for the moves of Bubble and Insertion Sort. Selection Sort’s swap count stays linear.

Question 4. Prove by induction that the Mergesort recurrence $T(1)=c$, $T(n)=2T(n/2)+dn$ (for $n=2^k$) has the closed form $T(n)=dn{\log }_{2}n+cn$. Then explain why $T(n)\in \Theta (n\log n)$.

Solution to Question 4

Claim: $T(2^k)=d{2}^{k}k+c{2}^k$ for all $k\ge 0$.

• Base ($k=0$): $T(1)=c=d\cdot 1\cdot 0+c\cdot 1$. ✓
• Step ($k\to k+1$):
  $T(2^{k+1})=2T(2^k)+d{2}^{k+1}\stackrel{\text{IH}}{=}2(d{2}^{k}k+c{2}^k)+d{2}^{k+1}=d{2}^{k+1}k+d{2}^{k+1}+c{2}^{k+1}=d{2}^{k+1}(k+1)+c{2}^{k+1}.✓$

With $n=2^k$, $k={\log }_{2}n$: $T(n)=dn{\log }_{2}n+cn$.
$\Theta$: for $n\ge 2$, $dn{\log }_{2}n\le T(n)\le (d+c)n{\log }_{2}n$ (using $n\le n{\log }_{2}n$ for $n\ge 2$). So $T\in O(n\log n)$ and $T\in \Omega (n\log n)$, hence $\Theta (n\log n)$.

Question 5. Design from an invariant. Take the invariant “after $j$ iterations, $A[\mathrm{1..}j]$ contains the $j$ smallest elements of $A$, sorted, at their final positions”. (a) Derive an algorithm that maintains it. (b) Give its comparison and swap counts. (c) How does it differ from Insertion Sort’s invariant?

Solution to Question 5

(a) Initialisation: $I(0)$ (empty prefix) holds trivially. To get from $I(j)$ to $I(j+1)$, position $j+1$ must receive the smallest element of the unsorted part $A[j+\mathrm{1..}n]$. Find it and swap it into position $j+1$:

for j := 0 to n-2:
    k := index of the minimum of A[j+1..n]
    swap A[k] and A[j+1]

Termination: $I(n-1)$ says the $n-1$ smallest elements are final, so the last element is the largest and also correct. Sorted.
This is Selection Sort mirrored (selecting minima from the front instead of maxima from the back).

(b) Finding the minimum of $n-j$ elements costs $n-j-1$ comparisons: ${\sum }_{j=0}^{n-2}(n-j-1)=\frac{n(n-1)}{2}=\Theta (n^2)$. Swaps: one per iteration, $n-1=O(n)$.

(c) Insertion Sort’s invariant requires only that the prefix be sorted, not that it hold the $j$ smallest elements at final positions. The weaker invariant is cheaper to establish (just insert the next element, $O(\log j)$ comparisons with binary search) but forces later shifting ($O(n^2)$ moves). The stronger “final positions” invariant forces a full scan per step ($\Theta (n^2)$ comparisons) but needs only $O(n)$ swaps. The choice of invariant determines the algorithm and its cost trade-off.