Slow and fast algorithms

slowVsFastAlgorithms.py

'''Course: https://www.coursera.org/learn/algorithmic-toolbox#about'''


def getFibonacciNumberForNSlow(number):
    '''very slow algorithms to get fibonacci number.
    Uses recursion (calls same function inside)'''

    assert number >= 0, "number should be greater than or equal to 0"

    if number <= 1:
        return number

    return getFibonacciNumberForNSlow(number-1) + getFibonacciNumberForNSlow(number - 2)




def getFibonacciNumberForNFast(number):
    '''very fast algorithm to get fibonacci number'''

    assert number >= 0, "number should be greater than or equal to 0"

    fibonacciList = []
    fibonacciList.append(0)
    fibonacciList.append(1)

    for i in range(2, number+1):
        fibonacciList.append(fibonacciList[i-1] + fibonacciList[i-2])

    return fibonacciList[number]




def getGreatestCommonDivisorSlow(number1, number2):
    '''slow algorithm to print greatest common divisor for 2 numbers'''

    greatestDivisor = 0

    for i in range(1, number1+number2):
        if number1%i == 0 and number2%i == 0:
            greatestDivisor = i

    print("get greatest common divisor slow: ", greatestDivisor, "\n")





def getGreatestCommonDivisorFastRecursive(number1, number2):
    '''very fast algorithm to print greatest common divisor for 2 numbers using Recursive approach
    It is called Euclidean algorithm'''

    assert number1 >= number2, "number1 should be greater than or equal to number2"

    if number2 == 0:
        return number1

    number1Hat = number1%number2
    return getGreatestCommonDivisorFastRecursive(number2, number1Hat)





def getGreatestCommonDivisorFastIterative(number1, number2):
    '''very fast algorithm to print greatest common divisor for 2 numbers using iterative approach
    It is called Euclidean algorithm'''

    assert number1 >= number2, "number1 should be greater than or equal to number2"


    while number2 != 0:

        temp = number2
        number2 = number1 % number2
        number1 = temp

    return number1








if __name__ == "__main__":

    print("get Fibonacci Value Fast: ", getFibonacciNumberForNFast(number=35))
    print("get Fibonacci Value Slow: ", getFibonacciNumberForNSlow(number=35), "\n")

    print("get greatest common divisor fast recursive: ", getGreatestCommonDivisorFastRecursive(number1=3918848, number2=1653264))
    print("get greatest common divisor fast iterative: ", getGreatestCommonDivisorFastIterative(number1=3918848, number2=1653264))
    getGreatestCommonDivisorSlow(number1=3918848, number2=1653264)