Skip to content

Solving Recurrence

Key Takeaways

  • \(n = 2^{\log_2n}\)
  • Constant size problems can be solved in constant time

Merge Sort

Algorithm

sort (A[1, n])
    if n = 1, return
    sort (A[1, ceil(n / 2)])
    sort (A[ceil(n / 2) + 1, n])
    merge(A[1, ceil(n / 2)], A[ceil(n / 2) + 1, n])

Master Theorem

Consider \(T(n) = a \cdot T\left(\frac{n}{b}\right) + n^c\) where \(a > 0, b > 1, c \geq 0\).

This recurrence means:

  • You split a problem of size \(n\) into a subproblems.
  • Each subproblem is of size \(n/b\).
  • The cost to split/merge/work at the current level is \(n^c\).

Recursion Tree Breakdown

  1. Top level (root):
    • Problem size: \(n\)
    • Work: \(n^c\)
  2. Level 1:
    • \(a\) subproblems of size \(n/b\)
    • Work per subproblem: \((n/b)^c\)
    • Total work at this level: \(a \cdot (n/b)^c\)

  3. Level 2:

    • \(a^2\) subproblems of size \(n/b^2\)
    • Work per subproblem: \((n/b^2)^c\)
    • Total work: \(a^2 \cdot (n/b^2)^c\)

    …

  4. Level \(i\):

    • Number of subproblems: \(a^i\)
    • Size of each: \(n / b^i\)
    • Total work: \(a^i \left(\frac{n}{b^i}\right)^c = a^i \cdot n^c \cdot b^{-ic} = n^c \cdot \left(\frac{a}{b^c}\right)^i\)

Depth of the tree:

  • Stop when \(n / b^i = 1 → i = \log_b n\)

That is, in the last level:

  • Number of subproblems: \(a^i = a^{\log_b n}\)
  • Work per subproblem: \(\frac{n}{b^{\log_b n}}=1\)

Total Work

Total work is the sum of the work across all levels:

\[ T(n) = \sum_{i=0}^{\log_b n} n^c \left(\frac{a}{b^c}\right)^i \]

This is a geometric series with ratio \(\frac{a}{b^c}\):

  • If \(\frac{a}{b^c} < 1\): the series converges, dominated by top level ⇒ \(T(n) = \Theta(n^c)\)
  • If \(\frac{a}{b^c} = 1\): each level does the same work ⇒ \(T(n) = \Theta(n^c \log_b n)\)
  • If \(\frac{a}{b^c} > 1\): increasing geometric sequence, bottom level dominates ⇒ \(T(n) = \Theta(a^{\log_b n}) = \Theta(n^{\log_b a})\)

Theorem

If \(T(n) = a \, T\left(\frac{n}{b}\right) + n^c\) for constants \(a > 0\), \(b > 1\), \(c \ge 0\), then

\[ T(n) = \begin{cases} O(n^c) & \text{if } c > \log_b a \\ O(n^c \log n) & \text{if } c = \log_b a \\ O(n^{\log_b a}) & \text{if } c < \log_b a \end{cases} \]

Remark: there are scenarios that the theorem does not apply but the proof method still works as we will see.

If the number of operations at each level increase in recurrence tree, the bottom level dominated, then we count the number of levels. If the number of operations at each level decreases, then we use Geometric Series.