REVISION AND PRACTICE
Week 2 Quick Revision
Start here All of Week 2 on one page: how to measure algorithms, Big O / Ω / Θ, how to count steps in loops and recursion, searching, and three sorting methods. Read this before a quiz; open the topic page if anything is unclear.
1. Measuring algorithms
- Two resources: time (main focus) and space.
- Running time t(n) is a function of the input size n.
- log n = log₂ n = number of halvings from n to 1. log₂ 10³ ≈ 10, log₂ 10⁶ ≈ 20, log₂ 10⁹ ≈ 30.
- Ignore constants; look at large n (asymptotic complexity).
- Growth order: 1 < log n < n < n log n < n² < n³ < 2ⁿ < n!
- Count basic operations, not seconds. A swap = 1 or 3 operations? Doesn't matter.
- For number problems, input size = number of digits (≈ log n), not n.
- We use the worst case: easier to calculate, and it's a guarantee.
- Python ≈ 10⁷ steps/second. In 1 second: n log n handles ~10⁶, n² ~3000, n³ ~200, 2ⁿ ~23.
2. Big O, Ω, Θ
| Definition (for n ≥ n₀) | Picture | |
|---|---|---|
| f is O(g) | f(n) ≤ c·g(n) | ceiling |
| f is Ω(g) | f(n) ≥ c·g(n) | floor |
| f is Θ(g) | c₁·g(n) ≤ f(n) ≤ c₂·g(n) | sandwich |
- To prove O: push every term up to the highest power, add the coefficients. 100n² + 20n + 5 ≤ 125n² for n ≥ 1.
- c and n₀ are not unique.
- n³ is not O(n²) (would need n ≤ c forever).
- f₁ + f₂ is O(max(g₁, g₂)) → the slowest phase decides.
- n(n−1)/2 is Θ(n²) with c₁ = 1/4, c₂ = 1/2, n₀ = 2.
- Comparison sorting needs Ω(n log n) — a lower bound for the problem.
3. Counting steps
| Code | Big O |
|---|---|
| One loop | O(n) |
| Nested loops (n × n), or all pairs i < j | O(n²) — pairs = n(n−1)/2 |
| Three nested loops (matrix multiply) | O(mnp) → O(n³) |
| Halving loop | O(log n) |
| T(n) = T(n−1) + 1 | O(n) |
| T(n) = T(n/2) + 1 | O(log n) |
| T(n) = 2T(n/2) + n | O(n log n) |
| M(n) = 2M(n−1) + 1 (Hanoi) | 2ⁿ − 1 → O(2ⁿ) |
4. Searching
- Linear search: O(n). Worst case = value not present.
- Binary search (sorted list only): check the middle, keep one half. O(log n). T(n) = T(n//2) + 1 = 2 + log n.
- Proving a value is absent in a sorted list needs only about log n looks.
- The slicing version (
l[:m]) copies the list — uselo/hipositions for true O(log n) time.
5. Sorting
| Selection sort | Insertion sort | Merge sort | |
|---|---|---|---|
| Idea | Pick the min of the rest, swap to front | Slide the next item into the sorted part | Split, sort halves, merge |
| Worst case | O(n²) | O(n²) | O(n log n) |
| Best case | O(n²) | O(n) (already sorted) | O(n log n) |
| In place? | Yes | Yes | No (needs a new list) |
| Invariant / key | L[:i] sorted | L[:i] sorted | merge is O(n) |
Watch out — mistakes in the slides
| Slide | What's wrong | Correct |
|---|---|---|
| 2.1 orders-of-magnitude table | n log n for n = 100 shown as 66 | 100 × 6.64 ≈ 664 |
| 2.6 iterative insertion sort | while(L[j] < L[j-1]): — no j > 0; crashes with IndexError | while j > 0 and L[j] < L[j-1]: |
| 2.6 recursive Insert | l[-1:] (small L) and else without : | L[-1:], else: |
| 2.4 binary search | slicing copies the list (not mentioned) | comparisons are O(log n), but slicing makes the time O(n); use lo/hi |
Practice questions
1. Arrange in increasing order of growth: n log n, 2ⁿ, log n, n², n, n!
log n < n < n log n < n² < 2ⁿ < n!2. Prove 6n² + 4n + 9 is O(n²). Give c and n₀.
For n ≥ 1: 4n ≤ 4n², 9 ≤ 9n². So 6n² + 4n + 9 ≤ 19n². c = 19, n₀ = 1.3. What is the time complexity?
<pre>for i in range(n): for j in range(i, n): count += 1</pre></summary>n + (n−1) + ... + 1 = n(n+1)/2 → <b>O(n²)</b>.</details>
4. What is the time complexity?
<pre>i = n while i > 0: i = i // 3</pre></summary>i is divided by 3 each time → about log₃ n rounds → <b>O(log n)</b>.</details>