HT2026 Design & Analysis of Algorithms notes


Remaining TODOs: 1

Relevant reading:

T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein. Introduction to Algorithms


1. Program cost and asymptotic notation

Definition 1.1:An algorithm is a finite set of well-defined instructions to accomplish a specific task.
Definition 1.2:An efficient algorithm runs in polynomial time.

Definition 1.3: Insertion sort compares each the element and compares it with the previously sorted elements, inserting it in the correct place.

In CRLS-style pseudocode (as used in Introduction to Algorithms):

Input: An integer array A
Output: Array A sorted in non-decreasing order
for j = 1 to A.length - 1
  key = A[J + 1]
  // insert A[j + 1] into the sorted sequence A[1..j]
  i = j
  while i > 0 and A[i] > key
    A[i + 1] = A[i]
    i = i - 1
  A[i + 1] = key

Definition 1.4: The running time of a CLRS program is defined as:

  • Line takes constant time
  • When a loop exits normally, the test is executed one more time than the loop body

Remark: The running time of insertion sort as given is where is the number of times the test of the while loop is executed for a given value of .

Then in the worst case, , so for some . Hence is quadratic in .

In the best case, so is linear.

Definition 1.5: Let . Then

If then is an asymptotic upper bound for .

Proposition 1.6: The algorithm is correct.

Proof:

By a loop-invariant argument:

  • Initialisation - Prove the invariant holds prior to first iteration
  • Maintenance - Prove that if holds just before an iteration, then it holds just before the next iteration
  • Termination: Prove that, when the loop terminates, the invariant along with the reason the loop terminates imply the correctness of the program

This is similar to mathematical induction, but rather than proving for all numbers, we expect to exit the loop.

Invariant: At the start of the th iteration, A[1..j] is sorted.

When , is a singleton so is trivially sorted.

The outer loop terminates when j = A.length. So the loop invariant at termination says that A[1..A.length] = A is sorted.

To prove maintenance, we need to prove that, at the end of the while loop, the sequence A[1], ..., A[i], key, A[i+2], ..., A[j+1] are sorted.

The invariant of the while loop is: TODO

Remark: Some nice properties of insertion sort:

  • It is stable (preserves relative order of equal keys)
  • In-place
  • Online (can sort the list as it is recieved)

Lemma 1.7: Let . Then:

Definition 1.8: If , we say that is an asymptotic lower bound for .
Corollary 1.9: .

Definition 1.10: If , is an asymptotic tight bound for .

Remark: Big // are not closed under function composition.