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

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开发者_如何学Python general method for converting between recursively-defined definitions to the more familiar direct type of expression?

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.

"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 nothing 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. There is no general algorithm for solving them.

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.