Running Time of Divide And conquer fibonacci program

Question

count = 0
def fibonacci(n):
    global count
    count = count + 1
    if not isinstance(n, int):
        print ('Invalid Input')
        return None

    if n < 0:
        print ('Invalid Input')
        return None

    if n == 0:
        return 0

    if n == 1:
        return 1

    fib = fibonacci(n-1) + fibonacci(n-2)
    return fib

fibonacci(8)
print(count)

I was trying to find out the running time of this fibonacci program. Can any one help me in solving the recurrence relation for the same..

T(n) = T(n-1) + T(n-2)...What would be the running time calculation from here?

Thanks... :)

Fibonacci and factorial are two completely different functions. Please make sure you know which you're talking about. :) — Karl Knechtel, Jul 10 '11 at 08:01
The isinstance is nugatory. The answer is that this implementation takes aeons! ;-) — David Heffernan, Jul 10 '11 at 08:36

score 1 · Answer 1 · edited May 23 '17 at 12:19

1

I am assuming you meant 'fibonacci' where you said 'factorial'.

At each level, you have two calls to fibonacci(). This means your running time will be O(2^n). You can see this by drawing the recursion tree.

For a much better and more detailed explanation, please see Computational complexity of Fibonacci Sequence.

edited May 23 '17 at 12:19

Community

1
1

answered Jul 10 '11 at 08:04

vinod

2,358
19
26

each two call doesn't mean 2^n, you can simply say too many algorithms are O(2^n) by this conclusion, for example MergSort has two call but it's n log n but we can say it's 2^n but it's not good estimation. – Saeed Amiri Jul 10 '11 at 09:08

score 0 · Answer 2 · answered Jul 10 '11 at 08:05

0

Take a look at this especially time.clock(). Call clock before your function call and after, calculate the difference and you got the elapsed time.

Btw: Why so much code for fibonacci?

def fib (n): return fib (n - 1) + fib (n - 2) if n > 1 else n

answered Jul 10 '11 at 08:05

Hyperboreus

31,997
9
47
87

Saeed Amiri · Accepted Answer · 2011-07-10T08:17:30.670

you can see wiki, But simple observation As you wrote:

 T(n) < 2T(n-1) = 2 * 2 T(n-2) =.... = 2^(n-1)T(1) = 2^(n-1). So T(n) is in O(2^n).

in fact you should solve x^2 = X + 1 so x will be phi1 = (1+sqrt(5))/2 or phi2 = (1-sqrt(5))/2 so result is phi1 ^ n + phi2 ^n but because phi2 is smaller than 1 for big n we can say it's T(n)=phi1^n.

Edit:*But you can edit your current solution to take O(n) running time(by for loop start from first element).

score 0 · Answer 4 · answered Jul 10 '11 at 09:00

The runtime is 2F(n+1) - 1 calls, where n is the nth Fibonacci number.

Here's a quick inductive proof:

As a base case, if n = 0 or n = 1, then we make exactly one call, and F(1) = F(2) = 1, and we have that 2F(n+1) - 1 = 1.

For the inductive step, if n > 1, then we make as many calls as are necessary to evaluate the function on n-1 and n-2. By the inductive hypothesis, this takes 2F(n) - 1 + 2F(n-1) - 1 = 2F(n+1) - 2 recursive calls to complete. However, because we count the current function call as well, we add one to this to get 2F(n+1) - 1 as required.

Note that 2F(n+1) - 1 is an expression for the nth Leonardo number, where

L(0) = L(1) = 1

L(n+2) = L(n) + L(n+1) + 1

Which grows at Θ(Φⁿ) as Saeed points out. However, this answer is mathematically exact.

This is more accurately the runtime you're interested in, since you need to account for the work being done in each recursive call itself. If you leave off the +1 term, you just get bac the Fibonacci series!

Running Time of Divide And conquer fibonacci program

4 Answers4