Different Functions, Same Output

The two functions shown below compute the \(n^\text{th}\) Fibonacci number.

For large values of \(n\), one of the functions is significantly faster than the other. Which function is faster, fib1 or fib2?

1
2
3
4
5
6
7
8
9
def fib1(n):
    if n == 0:
        result = 0
    elif n == 1:
        result = 1
    else:
        result = fib1(n - 1) + fib1(n - 2)

    return result 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def fib2(n):
    if n == 0:
        result = 0
    elif n == 1:
        result = 1
    else:
        a = 0
        b = 1
        for i in xrange(0, n - 1):
            result = a + b
            a = b
            b = result

    return result
×

Problem Loading...

Note Loading...

Set Loading...