Coursera Data Structures and Algorithms Specialization: Algorithm Warm-up(Week 2)

Courtesy of Unsplash

1. What can we learn from the Fibonacci Numbers problem?

The native implementation in Python is as follows:

def native_fib(n: int) -> int:
    if n<=1:
        return n
    else:
        return native_fib(n-1)+native_fib(n-2)

This inefficiency in the native implementation arises because the recursive approach involves solving the same subproblems multiple times. As a result, the time complexity grows exponentially, leading to slower performance, especially for larger Fibonacci numbers.

A more efficient algorithm is as follows:

def memo_fib_2(n: int) -> int:
    if n<=1:
        return n
    first = 0
    second = 1
    for i in range(2, n+1):
        current = first+second
        first = second
        second = current

    return second

The right algorithm matters as the efficient algorithm runs much faster than the native algorithm.

2. What can we learn from the Greatest Common Divisor problem?

The most popular method for the Great Common Divisor problem is the Euclidean Algorithm:

def gcd(x, y):
    # Euclidean algorithm 
    while y != 0:
        (x, y) = (y, x % y)
    return x

if __name__ ==…