How can I convert a function of input size defined recursively into a direct function of problem input size?

Question

Say I have an algorithm which operates on an input of size n and I know that the time it takes for n is twice the time it takes for n-1. I can observe in this simple case (assuming it takes, say, 1 second for n = 0) that the algorithm takes 2ⁿ seconds.

Is there a general method for converting between recursively-defined definitions to the more familiar direct type of expression?

Answer 1

Master Theorem

In particular:

With T(n) = aT(n/b) + n^c

If log_ba < c, then T(n) = O(n^c)

If log_ba = c, then T(n) = O(n^clog[n])

If log_ba > c, then T(n) = O(n^log_ba)

That's one useful theorem to know, but doesn't fully answer your question.

What you are looking for is the generator function of a recurrence relation. In general, these are only solvable for very simple cases, i.e. when f(n) = Af(n-1) + Bf(n-1) and f(0) = f(1) = 1 (or f(1) = A). Other recurrence relations are very difficult to solve.

See linear recurrence relation for more info.