Recurrence

Guess and Confirm

Have an induction hypothesis and confirm by an induction step

$$T(n) = \begin{cases} 2T(n-1) + 1 \\ T(0) = 0 \\ T(1) = 1 \end{cases}$$

I have a feel that this expands exponentially with an exponent of 2.

Suppose an induction hypothesis of $T(n) = 2^n - 1$.

Confirm with an induction step

$$\begin{align} T(n) &= 2T(n-1)+1 \notag \\ &= 2[2^{n-1} - 1] + 1 \\ & = 2^n - 2 + 1 \\ & = 2^n - 1 \end{align}$$

The recurrence is proved

Expanding Method

This works like a linked list (linear tree).

• Solve T(n) = T(n/2) + O(1) Answer: O(log n)

• Solve T(n) = T(n/2) + O(n) Answer: O(n)

• Solve T(n) = 2T(n/2) + O(n) Answer: O(nlogn)

Tree Method

As we have seen from the nlogn example, it is kind of hard to expand when we have more than one child.

• Solve T(n) = 2T(n/2) + O(n) Answer: O(nlogn)

• Solve T(n) = 2T(n/2) + O(1) Answer: O(n) Use the +1 trick, (1)+1+2+4+8+...+n = 2n-(1)

Master Theorem

We have generalize the tree method in 3 cases.

Reference

• Algorithms by Jeff Erickson - Solving Recurrences