CODEWITHSUNDEEP
algorithmtime-complexityfibonacci
La'tel
La'tel

Reputation: 127

Iterative fibonacci complexity, cannot undersant why it is O(n^2)

Please don't confuse the question with recursive fibonacci, which has the complexity 2^n.

This is the fibonacci iterative code i use : 

def f(n):
    a, b = 0, 1
    for i in range(0, n):
        a, b = b, a + b
    return a

I tried to find the complexity and i got it T(n) = n * 4 + 4 = 4n + 4, but the graph that i got is no linear at all and is more of a n^2. For example: 

print(timerf(250000)/timerf(50000))

This gives me result around 25.

I plotted a figure:

enter image description here

This shows that the fibonacci iterative method should be with complexity n^2. How to explain this?

Upvotes: 2

Views: 748

Answers (2)

maxim1000
maxim1000

Reputation: 6365

Iterative method complexity is O(n)*cost_of_addition

Usually people assume cost_of_addition to be a constant, but in case of Fibonacci numbers we quickly outgrow this assumption.

Since F(n) grows exponentially, number of digits in it is O(n). So the resulting complexity is O(n^2).

Upvotes: 6

Dmitry Zinkevich
Dmitry Zinkevich

Reputation: 3518

Maybe the reason is that addition of integers does not take constant time but linear - O(number of bits)

Upvotes: 1

Related Questions