If it gets called once per number in the sequence 0 to n, then we have O(n), if it gets called n times for each number, then we get O(n*n), or O(n^2), and so on. I came to the same conclusion by a rather simplistic but I believe still valid reasoning.įirst, it's all about figuring out how many times recursive fibonacci function ( F() from now on ) gets called when calculating the Nth fibonacci number. I agree with pgaur and rickerbh, recursive-fibonacci's complexity is O(2^n). You can find out this tight bound by using generating functions as I'd mentioned above. Consequently, the tight bound for this function is the Fibonacci sequence itself (~ θ(1.6 n )). Since each leaf will take O(1) to compute, T(n) is equal to Fib(n) x O(1). The value of Fib(n) is sum of all values returned by the leaves in the recursion tree which is equal to the count of leaves. The leaves of the recursion tree will always return 1.
An interesting fact about this function is that the T(n) is asymptotically the same as the value of Fib(n) since both are defined as However, as noted in a comment, this is not the tight bound. You can then prove your conjecture by induction. You solve this recurrence relation (using generating functions, for instance) and you'll end up with the answer.Īlternatively, you can draw the recursion tree, which will have depth n and intuitively figure out that this function is asymptotically O(2 n ).
This is assuming that repeated evaluations of the same Fib(n) take the same time - i.e.
Fibonacci sequence formula derivation plus#
You model the time function to calculate Fib(n) as sum of time to calculate Fib(n-1) plus the time to calculate Fib(n-2) plus the time to add them together ( O(1)). Since f(1)=1, f(2)=1 then we have the Fibonacci numbers (but starting from n=1 not n=0): month. The number of young is the same as the top entry of the previous month which is also the total of the month-before-that, ie f(n-2). The number of mature pairs is the total of the previous month, ie f(n-1). If f(n) is the total number of pairs in month n, then it is the sum of the mature in month n plus the young in month n. the bottom entry is the TOP entry of the previous month TOTAL. the top entry is the TOTAL of the previous month young. These two processes are summarized in this diagram: The number of young in any month is just the number of pairs that were mature the previous month, so we just copy the top entry to the bottom of the next column. In month 4, all those that were "young" the previous month become "mature", together with those who were "mature" from the previous month, so the top entry is the sum of the two entries in the column of the previous month. They give birth to a new pair in month 3.
Explanation: The young pair are introduced into the field and are immature in month 1. Returning to Fibonacci's original rabbits problem, let's enumerate how many mature rabbit pairs there are each month and how many immature pairs (1 month old): month: 1 2 3 4 5 mature: 1 1 2 3. It is optional and only recommended for those who have used matrices before.Īll you need to know is what a matrix is and how they multiply. A proof using Matrices This proof uses matrices and gives a practical application of - or introduction to - eigenvalues and eigenlines.
0 kommentar(er)
