I'm trying to calculate the T(n) for this function and what I have come up with is T(n) = T(n) + T(n) + O(1). I have the tow T(n) for 2 recursive calls to the function g() and then O(1) for all the constant time operations such as addition. I feel like I'm way off so any help would be greatly appreciated, my math background isn't too sound.
int g(int y) {
if (y <= 0) {
return 1;
}
else {
return g(y - 1) + g(y - 2);
}
}
The time complexity of computing Fibonacci numbers depends on the algorithm used. There are at least 4 algorithms for computing them (with different time complexities):
First we mention that we can figure this out by looking at the call graph of the recursive fibonacci function.
The callgraph is actually a tree.
We can reduce everything to finding out how many nodes this tree has.
The number of nodes in the call graph for F(n) has the root and the number of nodes in the call graph of F(n-1) + the number of nodes in the call graph of F(n-2).
We will denote the number of nodes in F(n) with L(n) (and you will see that the letter L is not accidental).
As we described above L(n) = L(n-1) + L(n-2) + 1.
But wait, there's more ! It turns out that these are exactly Leonardo numbers and they have the general closed form:
( "a(n) is the number of nodes in the Fibonacci tree of order n." A001595 )
There is another algorithm involving memoization that is of complexity O(n) (here is an example and another one). That involves storing the results of the T(n) in a vector and computing gradually T(n) for n=1 up to the required n.
If you want to be really really correct, this is not O(n) either, since the number cost of a addition is assumed to be O(1), however... as F(n) gets bigger, the cost of adding two fibonacci numbers is O(n). You can read more about this here , it is a fine exposition on this. And so, the actual complexity of this implementation is O(n^2).
There is also another algorithm of complexity O(1), given that you use arbitrary precision arithmetic or some smart rounding. It comes from Binet's formula. For a proof of Binet's formula see section 1.3 on page 13 here using generating functions or, you can find the eigendecomposition of the matrix and then use that to compute the nth power . After you do that, your closed-form formula will be in one of the cells of the nth power matrix.
If you want to be really precise, it's actually O(log(n)) since that's exponentiation by squaring (also called repeated squaring, binary powering algorithm or binary exponentiation) that you use to compute Binet's formula.
Usually we assume that the exponentiation of x^n is O(1), but it's not, it's O(log(n)) in the number of multiplications. To be really precise, you have to factor in the cost of a multiplication which depends on the multiplication algorithm used.
Here is Binet's formula btw:
Here is how the Fibonacci sequence looks in matrix form:
Here is exponentiation by squaring:
UPDATE 2015-06-29:
There's another approach to computing Fibonacci numbers in O(log(n)) . There are two identities being used
They allow the computation of F(2*n+1) based on F(n),F(n+1) and F(2*n) based on F(n-1),F(n),F(n+1). The algorithm finds the most significant bit of n and iterates down to the least significant bit while using the identities along the way to compute the fibonacci number. There's an implementation of the algorithm here. The two identities can either be derived(like in the previous link) in the quadratic field ℚ(√5) or they can be derived from n-th and 2n-th powers of the matrix mentioned above (see section 2.5 titled "Matrix Methods" on page 23 of "Algorithms for Computing Fibonacci Numbers Quickly" by J. L. Holloway).
The recurrence relation is as follows:
T(n) = T(n-1) + T(n-2) + O(1)
This won't fit any of the cases under the Master Theorem because you don't have a term in the form of T(n/b) in your equation.
Thus, we have to take a slightly odd approach:
Since T(n-1), by the above definition, would equal T(n-3) + T(n-2) + O(1), you can write T(n) as:
T(n) = 2T(n-2) + T(n-3) + 2*O(1)
Since, T(n-2) = T(n-3) + T(n-4) + O(1), we can further simplify T(n) as:
T(n) = 3T(n-3) + 2T(n-4) + 3*O(1)
By now, we should start seeing a pattern, but let's just take it one step further for good measure. Since T(n-3) = T(n-4) + T(n-5) + O(1):
T(n) = 5T(n-4) + 3T(n-5) + 4*O(1)
The coefficient of the first term is following the pattern of the fibonacci sequence. In the next round, we would have 8T(n-5) as the leading term. The second term is also following the fibonacci sequence, as in the next round we would have 5T(n-6). The third term is just growing as n does.
So, since T(1) is just O(1), you're going to end up with:
T(n) = x*O(1) + y*O(1) + n*O(1) where x is the nth term in the fibonacci sequence and y is the (n-1)th term in the fibonacci sequence.
Looking at the leading term, you can see that our big-O analysis is basically just whatever the formula is for calculating x based on n.
You can see that formula here: http://www.askamathematician.com/2011/04/q-is-there-a-formula-to-find-the-nth-term-in-the-fibonacci-sequence/
When you apply your big-O analysis, that will boil this all down to the following: O(1.6^n)
