Author: cyrus2281

Big O

How well a problem is solved

What is good code?

1. Readable
2. Scalable

import time
nemo = ['spam']*100000000 + ['nemo']

def findNemo(array):
    t0 = time.time()
    for a in array:
        if a == 'nemo':
            print("found nemo")
    t1 = time.time()
    print("The call took %u seconds" % (t1-t0))

findNemo(nemo)

found nemo
The call took 2 seconds

time doesn't mean anything

How does the efficiency of the function changes as the number of the elements increases?

Calculating Big O

Rules

1. Worst Cast
2. Remove Constants
3. Different terms for inputs
4. Drop Non Dominants

While calclating the big O, we always consider to worst case scenario. For example if we are searching in an array, we should assume that the element is the last element in the array

Constant values that don't have meaning should be remove. For example constant value of substaction, addition, multiplication, and division don't have meanings and can be removed. That means O(100+5n-n/2) can be simplified as O(n)

2 seperate inputs should have different notations. for example a function with inputs of 'a' and 'b' has a big O of O(a+b)

if there are multiple O values, we should only keep the one with the heighest dominance. For example in big o of n+n^2, the big o is n^2

Iterating through half a collection is still O(n)

Things to count

Operations (+, -, *, /)
Comparisons (<, >, ==)
Looping (for, while)
Outside Function call (function())

Big O notations

• Linear : O(n)
• Contant Time: O(1)
• Quadratic Time: O(n^2)
• Factorial Time: O(n!)
• Logarithmic Time: O(log n)
• Exponential Time: O(2^n)
• Log Linear Time: O(n log(n))

Linear

For loops, while loops through n items

def linear(ar):
    for a in ar: # O(n)
        print(a) # O(1)
# O(n)

Constant Time

No loops

def constantTime(ar):
    print(ar[0]) # O(1)
    print(ar[1]) # O(1)
# O(1)

Quadratic Time

Every element in a collection needs to be compared to ever other element. Two nested loops

def quadraticTime(ar):
    for a in ar: # O(n)
        for b in ar: # O(n)
            print(a,b) # O(1)
# O(n^2)

Factorial Time

you are adding a loop for every element

def factorialTime(num):  
    sum = 0
    if len(num) < 1:
        return 1
    for a in num:
        sum += factorialSum(num[1:])
    return sum
# O(n!)       

Logarithmic Time

usually searching algorithms have log n if they are sorted (Binary Search)

def binarySearch(arr, x):
    low = 0
    high = len(arr) - 1
    mid = 0
    while low <= high:
        mid = (high + low) // 2
        if arr[mid] < x:
            low = mid + 1
        elif arr[mid] > x:
            high = mid - 1
        else:
            return mid
    return -1

Exponential Time

recursive algorithms that solves a problem of size N

def exponentialTime(num):
    if num < 2:
        return num
    return fibonacci(num-1) + fibonacci(num-2)
# O(2^n)

Log Linear Time

usually sorting operations

def merge(left,right):
    result = []
    leftIndex = 0
    rightIndex = 0
    while leftIndex < len(left) and rightIndex < len(right):
        if left[leftIndex] < right[rightIndex]:
            result.append(left[leftIndex])
            leftIndex +=1
        else:
            result.append(right[rightIndex])
            rightIndex+=1
    return result+left[leftIndex:]+right[rightIndex:];
    
def mergeSort(lst):
    if len(lst) == 1:
        return lst
    mid = len(lst)//2
    return merge(mergeSort(lst[:mid]),mergeSort(lst[mid:]))
# O(n log n)

Space Complexity vs Time Complexity

time complexity is the amount of time needed for the function to execute
space complexity is the amount of memeory needed for the function to execute

What causes space complexity?

Variables
Data Structures
Function Call
Allocations

References

Instructors

• Andrei Neagoie: Master the Coding Interview: Data Structures + Algorithms

  https://academy.zerotomastery.io/p/master-the-coding-interview-data-structures-algorithms

Aditional Resources

• https://www.bigocheatsheet.com/