Fibonacci in time complexity of O(n)

# bottom-up dynamic programming 
def fib_dp(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        fib_list = [0, 1]
        for i in range(2, n + 1):
            fib_list.append(fib_list[i-1] + fib_list[i-2])
        return fib_list[n]

Explaination:

First, the function takes in an integer n as an argument, which represents the position of the Fibonacci number we want to calculate.

The function starts by checking if n is equal to 0 or 1. If it is, it immediately returns 0 or 1, respectively. This is because the first two numbers in the Fibonacci sequence are 0 and 1, so we can just return them directly without calculating anything.

Otherwise, the function creates an array called fib_list and assigns the values [0, 1] to it. This array will be used to store the previously calculated Fibonacci numbers, so that we can use them to calculate the next number in the sequence.

Then, the function enters a for loop that starts at index 2 and goes until n+1. This is because the first two numbers in the sequence have already been added to the fib_list array.

Inside the for loop, the function appends the sum of the previous two numbers in the fib_list array to the array. It does this by using the indices i-1 and i-2 to access the two previous numbers, and then adding them together.

At the end of the for loop, the function returns the last element of fib_list, which is the Fibonacci number at the position n.

This implementation uses a bottom-up dynamic programming approach, where we store the results of previously computed Fibonacci numbers in an array, and use them to calculate the next number in the sequence. This avoids the need to re-compute the same numbers multiple times, which reduces the overall time complexity, and makes it O(n) .

Examples of time complexity of O(2^n)

def fib_rec(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib_rec(n-1) + fib_rec(n-2)

This implementation has a time complexity of O(2^n) because each call to the function generates two new calls, one for n-1 and one for n-2. Therefore, the total number of calls grows exponentially with the input size. For example, to calculate the 30th Fibonacci number, we would need to make more than 2 billion function calls.

The problem with this implementation is that it recalculates the same Fibonacci numbers over and over again, leading to a lot of redundant computation. For example, to calculate fib_rec(4) we need to calculate fib_rec(3) and fib_rec(2), but to calculate fib_rec(3) we also need to calculate fib_rec(2), which is redundant.

This is why the bottom-up dynamic programming approach has a better time complexity. It avoids the redundant computation by storing the already calculated values in an array and uses them to calculate the next values in the sequence.