DC3: Recurrences

Question 1

Describe the general approach to solving a recurrence

Answer 1

Using either expansion or a recursion tree, we get a geometric series sum of i = 1 to k of alpha^i where alpha is a fraction and k is the final recursion.

When alpha < 1, the first term dominates so it’s O(1)
When alpha > 1, the last term dominates so it’s O(alpha^k)
When alpha = 1, we sum up all terms and get O(k) (when the work at each level is O(1))

Question 2

An important bit of algebra: how do we get an exponent of the form n^c from x ^ log_b n?

Answer 2

x ^ log_b n = n ^ log_b x, i.e., we just swap x and n.