Lecture Notes: 6.046 - Lecture 2

Introduction

Lecturer: Eric Dain
Focus: Mathematical underpinnings from Lecture 1
- Algorithms analyzed: Insertion Sort, Merge Sort
- Main topics for today:
  - Asymptotic notation
  - Solving recurrences

Big O Notation (Upper Bound)
- Definition: F(n) = O(G(n)) means constants C and N exist such that for all n >= N, |F(n)| <= C|G(n)|
- Used to express an upper bound on the function's growth
- Example: 2n^2 = O(n^3)
- Not symmetric: n^3 not O(n^2)
- Can be written as a set of functions: O(G(n)) = {F(n) : F(n) <= C|G(n)| for n >= N}
Big Omega Notation (Lower Bound)
- Definition: F(n) = Ω(G(n)) means constants C and N exist such that for all n >= N, |F(n)| >= C|G(n)|
- Expresses a lower bound on the function's growth
- Example: √n = Ω(log n)
Theta Notation (Tight Bound)
- Definition: F(n) = Θ(G(n)) means F(n) is bounded both above and below by G(n) up to constant factors
- Example: n^2 + O(n) = Θ(n^2)
Little o Notation (Strict Upper Bound)
- Definition: F(n) = o(G(n)) means for every constant C > 0, there exists an N such that for all n > N, |F(n)| < C|G(n)|
- Expresses stricter version of Big O
- Example: n^2 = o(n^3)
Little Omega Notation (Strict Lower Bound)
- Definition: F(n) = ω(G(n)) means for every constant C > 0, there exists an N such that for all n > N, |F(n)| > C|G(n)|
- Example: n^3 = ω(n^2)

Substitution Method
- Step 1: Guess the form of the solution
- Step 2: Prove the guess by induction
- Example Recurrence: T(n) = 4T(n/2) + n
  - Guess: T(n) = O(n^3)
  - Proof by induction:
    - Base Case: T(1) ≤ C
    - Induction Step: Prove T(n) ≤ Cn^3
  - Strengthening the hypothesis to find exact bounds might be necessary (e.g., consider lower order terms)

Concept
- Visualize the recurrence as a tree and sum the costs level by level
- Example: T(n) = 2T(n/2) + n
- Draw the tree and collapse levels to identify dominant terms
- Useful for recognizing geometric series

Form: T(n) = aT(n/b) + f(n)
- Conditions: a >= 1, b > 1, f(n) positive asymptotically
- Compare f(n) with n^log_b(a)
- Three Cases:
  - Case 1: f(n) = O(n^log_b(a) - ε) for some ε > 0 → T(n) = Θ(n^log_b(a))
  - Case 2: f(n) = Θ(n^log_b(a) log^k(n)) for some k ≥ 0 → T(n) = Θ(n^log_b(a) log^(k+1)(n))
  - Case 3: f(n) = Ω(n^log_b(a) + ε) for some ε > 0
    - Additional requirement: af(n/b) ≤ cf(n) for some c < 1 and sufficiently large n
    - T(n) = Θ(f(n))
- Application Examples:
  - T(n) = 4T(n/2) + n: Solution T(n) = Θ(n^2) (Case 1)
  - T(n) = 4T(n/2) + n^2: Solution T(n) = Θ(n^2 log n) (Case 2)
  - T(n) = 4T(n/2) + n^3: Solution T(n) = Θ(n^3) (Case 3)
- Non-Master Theorem Example:
  - T(n) = 4T(n/2) + n^2/log n: Does not fit cases; different approach needed.