Analyzing Algorithms
This chapter develops the machinery for analysing algorithms rigorously: proving correctness with loop invariants, the assumptions behind our cost model, and computing best-, worst-, and average-case running times. We apply these tools to insertion sort, linear search, binary search (introducing recurrence relations along the way), and selection sort.
3.1Insertion Sort
Insertion sort works the way many people sort playing cards: keep the left part of the array sorted, take the next element (the key), and insert it into its correct position by shifting larger elements one place to the right.
INSERTION-SORT(A, n) 1. for i = 2 to n 2. key = A[i] 3. // Insert A[i] into the sorted subarray A[1 : i−1] 4. j = i − 1 5. while j > 0 and A[j] > key 6. A[j + 1] = A[j] 7. j = j − 1 8. A[j + 1] = key
A[1 : i−1] holds the elements originally in
A[1 : i−1], but in sorted order.
3.2Correctness: The Loop Invariant Technique
To prove the correctness of algorithms, we typically use the loop invariant technique. Using a loop invariant, we show three things:
- Initialization — the invariant holds true before the loop starts.
- Maintenance — it remains true after every iteration of the loop.
- Termination — when the loop finishes, the invariant helps prove that the algorithm is correct.
Applying it to insertion sort
| Step | Argument |
|---|---|
| 1. Initialization (base case) |
Before the first iteration (i = 2), A[1] is trivially sorted — a single element. So the invariant holds. |
| 2. Maintenance (inductive step) |
Assume A[1 : i−1] is sorted before iteration i. The algorithm inserts A[i] (the key) into its correct position in A[1 : i] by shifting larger elements right. After insertion, A[1 : i] is sorted — the invariant is preserved. |
| 3. Termination | The loop ends at i = n + 1. At this point the invariant tells us that A[1 : n] — the full array — is sorted. |
3.3Key Assumptions in Algorithm Analysis
| Assumption | Meaning |
|---|---|
| 1. Sequential execution | Instructions are executed one after another; no concurrent operations allowed. |
| 2. Equal cost for similar instructions | Data access or updating a variable of a given data structure takes constant time. |
| 3. No unrealistic assumptions | For example, we cannot assume sorting an array takes constant time. |
| 4. Ignoring precision & word size | Floating-point precision is ignored; values may be big but not infinite; the word size is enough to hold input values and intermediate results. |
| 5. Memory access assumption | The memory hierarchy (caches, RAM vs disk) is ignored. |
3.4What is Input Size?
The right notion of "input size" depends on the problem:
- Sorting — determined by the number of elements in the array or list.
- Graph problems — defined by the number of vertices (V) or edges (E).
- Multiplication — depends on the number of bits required to represent the two numbers.
3.5Calculating Running Time
Let a statement take ck steps (CPU cycles) to execute.
If it is executed m times, its total contribution is:
| Line | Statement | Cost | Times executed |
|---|---|---|---|
| 1 | for i = 2 to n | c₁ | n |
| 2 | key = A[i] | c₂ | n − 1 |
| 3 | insert into sorted prefix | 0 | n − 1 |
| 4 | j = i − 1 | c₄ | n − 1 |
| 5 | while j > 0 and A[j] > key | c₅ | Σ tᵢ |
| 6 | A[j + 1] = A[j] | c₆ | Σ (tᵢ − 1) |
| 7 | j = j − 1 | c₇ | Σ (tᵢ − 1) |
| 8 | A[j + 1] = key | c₈ | n − 1 |
T(n) = c₁n + c₂(n − 1) + c₄(n − 1)
+ c₅Σi=2n tᵢ
+ c₆Σi=2n (tᵢ − 1)
+ c₇Σi=2n (tᵢ − 1) + c₈(n − 1)
3.6Insertion Sort: Best, Worst, and Average Case
The while-loop condition A[j] > key fails immediately in every
iteration, so no shifting happens: every tₙ = 1.
show answer
tᵢ = 1 for every i
Σ(tᵢ − 1) = 0
Tbest(n) = an + b = Θ(n)
Every key must be compared with, and shifted past, all elements to its left, so every tₙ = i: the while loop runs the maximum possible number of times.
show answer
tᵢ = i
Σi=2n i = n(n + 1)/2 − 1
Σi=2n (i − 1) = 1 + 2 + ⋯ + (n − 1) = n(n − 1)/2
Tworst(n) = c₁n + c₂(n − 1) + c₄(n − 1)
+ c₅[n(n + 1)/2 − 1]
+ (c₆ + c₇)[n(n − 1)/2] + c₈(n − 1)
Tworst(n) = an² + bn + c = Θ(n²)
How long does it take to find where in A[1 : i−1] to insert A[i] for a random instance?
show answer
On average, half the elements in A[1 : i−1] are greater than A[i], so tₙ ≈ i/2 — about half the worst-case shifts. Halving the sum only halves the constant, so the resulting average-case running time is still a quadratic function of the input size, just like the worst case.
3.7Asymptotic Behaviour of Running-Time Expressions
T(n) = n²/100 + 100n + 7
show answer
The n²/100 term dominates when n is much larger than 10,000, and lower-order terms become negligible for large n. This is why analysis focuses on the fastest-growing term — the idea behind asymptotic notation, coming in the next chapter.
3.8Linear Search
Algorithm steps
- Start from the first element of the array.
- Compare the key with the current element.
- If the key matches the current element, return its index.
- If it does not match: if the list has not ended, move to the next element and go to step 2; else return −1.
LINEAR-SEARCH(A, x) 1. for i = 1 to n 2. if A[i] == x 3. return i 4. return NIL
3.9Linear Search: Case Analysis
Take arr = [3, 8, 7, 1, 9]:
| Case | Example | Comparisons | Time |
|---|---|---|---|
| Best case | key = 3 (first element) | 1 | constant |
| Worst case | key = 9 (last element or absent) | 5 (= n) | linear n |
| Average case | key can be present anywhere | (n + 1)/2 = all possible cases / total cases | linear n |
3.10Linear Search: Properties and Correctness
Key characteristics
- Works on both sorted and unsorted arrays.
- Time complexity varies based on the position of the target element.
Advantages
- Simple and easy to implement.
- Works on both sorted and unsorted arrays.
- Requires no preprocessing of the array.
Disadvantages
- Inefficient for large datasets.
- Performance degrades linearly with the size of the array.
Correctness via loop invariant
Invariant: at the start of iteration i, x is not in A[1 : i−1].
| Step | Argument |
|---|---|
| Initialization | Before the first iteration (i = 1), the subarray A[1 : 0] is empty, so the invariant holds. |
| Maintenance | Assume the invariant holds at iteration i, so x ∉ A[1 : i−1]. If A[i] = x we return i (correct); else we move to i + 1 and the invariant is maintained. |
| Termination | When the loop ends, all of A[1 : n] has been checked; the invariant ensures x is not in the array, so returning NIL is correct. |
3.11Exercises
- Modify linear search to count occurrences of a target element.
- Use linear search to find the largest / smallest element in an array.
- What is the best-case, worst-case, and average-case execution time for the above problems?
show answer
Counting occurrences: the loop can never return early — every element must be
checked even after a match — so best = worst = average = n comparisons.
Largest / smallest element: one pass keeping a running max (or min) always makes
n − 1 comparisons, regardless of the input order — again best = worst = average ≈ n.
The lesson: early exit is what separated linear search’s best case (1) from its worst (n);
remove the early exit and all three cases collapse together.
3.12Binary Search — Search Smart, Not Hard!
If the array is sorted, we can do much better than checking every
element. Binary search keeps two pointers, low and
high, computes the middle index
mid = (low + high) / 2, and compares
A[mid] with the key:
- If
A[mid] == key→ return mid. - If
A[mid] > key→ discard the right half:high = mid − 1. - If
A[mid] < key→ discard the left half:low = mid + 1.
Tracing the lecture example — searching key = 33 in a 15-element sorted array: mid = (0+14)/2 = 7 gives A[7] = 53 > 33, so high = 6; mid = (0+6)/2 = 3 gives A[3] = 25 < 33, so low = 4; mid = (4+6)/2 = 5 gives A[5] = 43 > 33, so high = 4; finally mid = (4+4)/2 = 4 and A[4] = 33 — found.
3.13Binary Search: Algorithm
BinarySearch(array, key):
1. Set low = 0
2. Set high = length(array) − 1
3. While low <= high:
a. Set mid = low + (high − low) // 2
b. If array[mid] == key:
return mid
c. Else if array[mid] < key:
Set low = mid + 1
d. Else:
Set high = mid − 1
4. return −1 // Target not found
3.14Binary Search: Execution Time Analysis
Each step halves the search space: n → n/2 → n/4 → … → 1. The number of
halvings until one element remains is log n
(compare the halving loop from Chapter 2:
for (int i = n; 1 < i; i = i/2)).
As a recurrence relation
At each step, the algorithm divides the input into two halves, performs a single comparison, and decides whether to search the left or right half:
T(n): time for input size n · T(n/2): time for the reduced input after one division · c: constant time for the comparison and midpoint calculation.
Solving by the substitution method
T(n) = T(n/2) + c
= T(n/4) + c + c
= T(n/8) + c + c + c
⋮
= T(n/2ᵏ) + k·c = T(1) + k·c
where n/2ᵏ = 1, so k = log n
Cases
| Case | When | Time |
|---|---|---|
| Best | The target is found on the first comparison. | O(1) |
| Worst | The search interval shrinks to size 1 (target absent or found at the last step). | O(log n) |
| Average | The element is found after searching half the depth of the search tree. | O(log n) |
3.15Selection Sort
Selection sort repeatedly finds the minimum element of the unsorted part and places it at the front:
SELECTION-SORT(A, n) 1. for i ← 0 to n − 2 do 2. min_index ← i 3. for j ← i + 1 to n − 1 do 4. if A[j] < A[min_index] then 5. min_index ← j 6. end for 7. if min_index ≠ i then 8. swap A[i] and A[min_index] 9. end for
Execution time as a recurrence
At each step the algorithm reduces the input size by one: it performs n−1 comparisons and puts the current minimum element in its correct position.
T(n): time for input size n · T(n−1): time for the reduced input after one step · c: constant time per comparison.
Solving this recurrence (try expanding it like the binary search one!) gives c·[(n−1) + (n−2) + … + 1] = c·n(n−1)/2 — a quadratic function of n, regardless of the input order.