BigO.py

"""
BigO Notation
    Big O Notation is used to measure hoe running time or space requirements for your program grow as input size grows
Order of Magnitude
    A Time Complexity does not tell the exact number of times the code inside a loop is executed,
    but it only shows the order of magnitude. Whether code inside loop is executed for 3n, n+5, n/2 times;
    the time complexity of each code is O(n)

Rules for BigO Notation
    time = a * n + b
    > Keep fastest growing term
            BigO refers to very large value of n. Hence if you have a function like:
                time = 5*n^2 + 3*n + 20
                when value of n is very large (b*n + c) become irrelevant
                Example: n = 1000
                time = 5*1000^2 + 3*1000 + 20
                time = 5000000 + 3020
                time ~= 5000000  # terms other than 5*1000^2 contribute negligible

        time = a * n  # being b a constant and static

    > Drop constant
        time = n  # a being constant
        time = O(n)

Measuring running time growth (Time Complexity)

    Constant Time Complexity O(1)
        Running time of Constant-time algorithm does not depend on the input size
        time = a
        time = O(1)  # applying rules for Big O :: Keep fastest growing term (a) ->->-> Drop Constants(a)


        def foo(a):  # time is nearly constant with increase in input size
            size(arr) : 100   -> 0.22 milliseconds
            size(arr) : 1000  -> 0.23 milliseconds

    Logarithmic Time Complexity O(log n)
        A logarithmic algorithm often halves the input size at each step. The running time of such an algorithm is
        logarithmic, because log2 n equals the number of times n must be divided by 2 to get 1

    Square Root Algorithm O(sqrt(n))
        A square root algorithm is slower than O(log n) but faster than O(n) A special property of square roots is that
        sqrt(n) = n/(sqrt(n)), so the square root (sqrt(n)) lies, in some sense, in the middle of the input

    Linear Time Complexity O(n)
        A linear algorithm goes through the input a constant number of times
        time = a * n + b
        time = O(n)  # applying rules for Big O :: Keep fastest growing term (a*n) ->->-> Drop Constants(a, b)

        def foo(arr):
            size(arr) : 100   -> 0.22 milliseconds
            size(arr) : 1000  -> 2.30 milliseconds

    O(n log n)
        This time complexity often indicates that the algorithm sorts the input, because the time complexity of
        efficient sorting algorithms is O(n logn)

    Quadratic Time Complexity O(n^2)
        A quadratic time complexity often contains two nested loops
        time = a * (n^2) + b
        time = O(n^2)  # applying rules for Big O :: Keep fastest growing term (a*n^2) ->->-> Drop Constants(a, b)
        Exception O(n^2) not O(n^2 + n)
            time = a*(n^2) + (b * n) + c
            time = n^2  # applying rules for Big O :: Keep fastest growing term (a*n^2) ->->-> Drop Constants(a, b, c)

    Cubic Time Complexity O(n^3)
        A cubic algorithm often contains three nested loops

    O(2^n)
        This time complexity often indicates that the algorithm iterates through all subsets of the input elements

    O(n!)
        This time complexity often indicates that the algorithm iterates through all permutations of the input elements

    Note:
        An algorithm is polynomial if its time complexity is at most O(nk) where k is a constant.
        All the above time complexities except O(2n) and O(n!) are polynomial

Given the input size, we can try to guess the required time complexity of the algorithm that solves the problem.
The following table contains some useful estimates assuming a time limit of one second

    n <= 10     O(n!)
    n <= 20     O(2n)
    n <= 500    O(n3)
    n <= 5000   O(n2)
    n <= 106    O(n logn) or O(n)
    n is large  O(1) or O(log n)


"""
""" Time Complexity """

# Linear Time Complexity O(n)
def squareNum(numbers):
    """
    Time Complexity: O(n)  :: loop will iterate n time linearly
    """
    sqNum = []  # empty array for squared numbers initialised
    for n in numbers:  # loop will iterate n times
        sqNum.append(n*n)
    return sqNum


# Constant Time Complexity O(1)
def findPE(prices, eps, index):
    pe = prices[index] / eps[index]
    return pe


# O(n^2)
def duplicateInArray(numbers):
    """ Running two for loops"""
    duplicate = None
    # (n^2) iterations
    for i in range(len(numbers)):
        for j in range(i+1, len(numbers)):
            if numbers[i] == numbers[j]:
                print(f"{numbers[i]} is duplicate")
                duplicate = numbers[i]
                break
    # n iterations
    for i in range(len(numbers)):
        if numbers[i] == duplicate:
            print(i)


""" Space Complexity """
def Search(numbers):
    """
    Search for 10 in list
    Time Complexity: O(n)
    """
    for i in range(len(numbers)):
        if numbers[i] == 10:
            print(i)




if __name__ == '__main__':
    # O(n)
    numbers = [2, 5, 7, 9]
    print(squareNum(numbers))

    # O(1)
    prices = [250, 500, 450]
    eps = [25, 50, 75]
    index = 1
    print(findPE(prices, eps, index))

    # O(n^2)
    numbers = [2, 4, 6, 8, 14, 9, 4]
    duplicateInArray(numbers)

    numbers = [1, 6, 8, 10, 4, 5]
    Search(numbers)