CODEWITHSUNDEEP
pythonpython-3.x
user10732646
user10732646

Reputation:

Fibonacci: Time Complexity and Big O Notation

I have seen several solution of Fibonacci from different tutorials site and one thing that I noticed is that they have the same way of solving the problem through recursive function. I tested the recursive function and it takes 77 seconds before I get the 40th item in the list so I tried to make a function without dealing recursive function through a for loop and it only takes less than a second. Did I made it right? What is the O notation of my function?

from time import time


def my_fibo(n):
    temp = [0, 1]
    for _ in range(n):
        temp.append(temp[-1] + temp[-2])
    return temp[n]


start = time()
print(my_fibo(40), f'Time: {time() - start}')
# 102334155 Time: 0.0

vs

from time import time
def recur_fibo(n):
    if n <= 1:
        return n
    else:
        return recur_fibo(n - 1) + recur_fibo(n - 2)


start = time()
print(recur_fibo(40), f'Time: {time() - start}')
# 102334155 Time: 77.78924512863159

Upvotes: 1

Views: 1174

Answers (2)

Gustavo Kaneto
Gustavo Kaneto

Reputation: 683

The answer is above, for the big-O: in the classical recursive implementation that you showed, the function calls itself two times in each pass.

In the example below, I wrote a recursive function that calls itself just one time in each pass, so it also has an O(n):

def recur_fibo3(n, curr=1, prev=0):
    if n > 2: # the sequence starts with 2 elements (prev and curr)
        newPrev = curr
        curr += prev
        return recur_fibo3(n-1, curr, newPrev) # recursive call
    else:
        return curr

It performs linearly with increases in n, but it is slower than a normal loop.

Also, you can note that both recursive functions (the classical and the above one) do not store the whole sequence for you to return it. Your loop-function do this, but if you just want to retrieve the n-th value in the series, you can write a faster function somewhat like this:

def my_fibo2(n):
    prev1 = 0
    prev2 = 1
    for _ in range(n-2):
        curr = prev1 + prev2
        prev2 = prev1
        prev1 = curr
    return curr

Using %timeit to measure execution times, we can see which one is faster. But all of them are fast enough in normal conditions, because you just need to calculate a long series once and store the results for later uses... :)

Time to return the 100th element in Fibonacci series

my_fibo(100)
10.4 µs ± 990 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

my_fibo2(100)
5.13 µs ± 1.68 µs per loop (mean ± std. dev. of 7 runs, 100000 loops each)

recur_fibo3(100)
14.3 µs ± 2.51 µs per loop (mean ± std. dev. of 7 runs, 100000 loops each)

============================================
Time to return the 1000th element in Fibonacci series

my_fibo(1000)
122 µs ± 10.5 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

my_fibo2(1000)
82.4 µs ± 17.3 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

recur_fibo3(1000)
207 µs ± 19.5 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

Upvotes: 0

Andrew Fan
Andrew Fan

Reputation: 1322

What you have done is an example of the time-space tradeoff.

In the first (iterative) example, you have an O(n) time algorithm that also takes O(n) space. In this example, you store values so that you do not need to recompute them.

In the second (recursive) example, you have an O(2^n) time (See Computational complexity of Fibonacci Sequence for further details) algorithm that takes up significant space on the stack as well.

In practice, the latter recursive example is a 'naive' approach at handling the Fibonacci sequence and the version where the previous values are stored is significantly faster.

Upvotes: 2

Related Questions