Measuring Code Complexity and Efficiency

code_complexity_efficiency.py

# Measure complexity as a function of input size
# - Worst case scenario
# - Largest factor in expression

# Asymptotic Notation - provide a formal way to talk about the relationship between
#                       the running time of an algorithm and the size of inputs.
#
# Asymptotic notation describes the complexity of an algorithm as the size of it's
# inputs approaches infinity

# The most commonly used asymptotic notiation is called:
# Big O Notation - Used to give an upper bound on asymptotic growth of a function
# - O(1) denotes constant running time
# - O(log n) denotes logarithmic running time
# - O(n) denotes linear running time
# - O(n log n) denotes log-linear running time
# - O(n^k) denotes polynomial running time time. k is a constant
# - O(c^n) denotes exponential running time. Constant is being raised to a power based
#         on size of input

# O(1) - Constant Complexity
# - Complexity is independant of input size.
# - Can include loops and recursive calls, but the numer of iterations has to be 
#   independent of the size of inputs
# - We consider all mathematical operations are constant time
# Example:
def mul(x, y):
    return x * y

def foo(x):
    y = x * 77.3
    return x / 8.2

# O(log n) - Logarithmic Complexity
# - Complexity grows as the log of at least one of the inputs
# - Complexity grows really slowly
# - Bisection search, Binary search of a list
# Example:
def int_to_str(i):
    """
    Convert a positive integer to a string value.
    """
    digits = '0123456789'
    if i == '0':
        return '0'
    
    result = ''
    while i > 0:
        result = digits[i % 10] + result # index into digits
        i = i / 10 # remove right most digit
    
    return result

# O(n) - Linear Complexity
# - Functions and/or algorthims that deal with lists or other kinds of sequences
#   are linear becuase they touch each element of the sequence a constant (> 0)
#   number of times.
# - Program does not have to have a lopp to have linear complexity (recusive calls)
# Example:
def add_digits(s):
    """
    Take a string of digits, add them, and return the sum.
    
    Func is linear to the length of s; only goes through s 1 time
    """
    val = 0
    for c in s:
        val += int(c)
    return val

# Another linear example:
def get_factorial(n):
    if n == 1:
        return 1
    else:
        return n * get_factorial(n-1)

# O(n log n) - Log Linear Complexity
# - Complexity based on product of two terms, each which depends upon the size
#   of inputs.
# - The most commonly used log-linear algorithm is merge sort

# O(n^k) - Polynomial Complexity
# - Most commonly used polynomial algorithms are quadratic, i.e. their complexity
#   grows as the squre of the size of their input
# - Remember k is a constant, unlike exponential
# - n^2 = 100 10000 1000000
# Example:
def is_subset(L1, L2):
    """
    Check two lists and return True if each element in L1 is also in L2; False otherwise
    """
    for e1 in L1:
        matched = False
        for e2 in L2:
            if e1 == e2:
                matched = True
                break
        if not matched:
            return False
    return True

# The function will execute the outer loop O(len(L1)), which will reach the
# inner loop O(len(L1)) times. The inner loop will execute O(len(L2)) times.
# Therefore the is_subset func is O(len(L1) * len(L2))

# - O(c^n) - Exponential Complexity
# - c^n = c^10 c^100 c^1000



#############################################################################
# 1) 5n
# O(n)
#
# 2) 3n^2 + 2n − 100
# O(n^c)
#
# 3) 10log(n) + 5n
# O(n)
#
# 4) 10log(n) + 5n^2
# O(n^c)
#
# 5) 3n^3 − 2000n^2
# O(n^c)
#
# 6) 1000+2000000
# O(1)
#
# 7) log n + 1000
# O(log(n))