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.

Answer 2

"Recursive functions" like this are called Recurrence Relations, and their "direct types" are known as the Closed-form solution.

While the Master Theorem listed by Poita is very helpful in computing time-complexity, it has little to do with actually solving recurrence relations.

Wikipedia and Wolfram's Math World (under "See Also") list the closed-forms of some common classes of recurrence relations. However, complicated (non-linear) recurrence relations can be very difficult to find closed-form solutions to, if one exists at all.

Answer 3

If it's linear, you can express the relation as a matrix and find the Eigen values, decomposing it into a form that lets you raise the eigen values to a power, as worked through for Fibonacci here.

Answer 4

If you have a deeper interest in such topics check Concrete Mathematics by Donald Knuth. It shows how you can derive the closed form of a recurrence relation.