Recurrence

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.