Recurrences

How to solve?

• Solving by unrolling.
• Solving with a guess and inductive proof.
  • Solving using a recursion tree.
• A master formula.

Master Formula

$$T(n) = aT(\frac{n}{b})+ cn^k, T(1) = c$$

for positive constants $$a, b, c, k$$

If we define $$r = \frac{a}{b^k}$$

$$r < 1 \implies T(n) = \Theta(n^k)$$

$$r = 1 \implies T(n) = \Theta(n^k\log{n})$$

$$r > 1 \implies T(n) = \Theta(n^{\log_b{a}})$$