Algorithms: Big O Notations

Introduction

An algorithm is a series of steps that can be followed to solve a problem. Algorithms are the foundation of computer science, and they’re used in everything from web search engines to video games. The word “algorithm” comes from the 9th-century Persian mathematician Muġammad ibn Mūsā al-Khwārizmī, who wrote down his procedures in order to solve equations. To understand an algorithm’s time complexity or space complexity — how long it takes or how much space it uses — we use Big O notation. This notation describes an algorithm’s worst-case execution time and worst-case space usage on any given input. Let’s take a look at what this means!

Big O notation is a way to describe the complexity of an algorithm.

Big O notation is a way to describe the complexity of an algorithm. It’s used to compare algorithms with each other and determine which one will be more efficient in terms of time and space. Big O notation represents the growth rate of an algorithm, where lower-order functions grow much slower than higher-order functions.

We use Big O notation to discuss time and space.

Big O notation is a way of describing the worst-case time and space of an algorithm. In other words, it’s used to compare different types of algorithms by how much memory they use or how long they take to run.

Big O notation can be used for both time and space, but we’ll only discuss its application in terms of space here because it’s easier to understand if you’re new to this topic. If you’re interested in learning more about Big O notation as it relates to time complexity, check out our companion article!

Big O describes worst-case execution time and worst-case space, given a certain input.

Big O notation is used to describe the worst case execution time and space, given a certain input.

The most common use of big O notation is in comparing algorithms. For example, if you want to know whether one algorithm is better than another, you can compare their running times by looking at their big O complexities. This will tell you whether one algorithm runs faster than another on average or not; it won’t tell you anything about how long each individual run will take (but this may be useful information too).

Examples:

# Array
nums = [1, 2, 3]
nums.append(4)    # push to end
nums.pop()        # pop from end
nums[0]           # lookup
nums[1]
nums[2]


# HashMap / Set
hashMap = {}
hashMap["key"] = 10     # insert
print("key" in hashMap) # lookup
print(hashMap["key"])   # lookup
hashMap.pop("key")      # remove

nums = [1, 2, 3]
sum(nums)           # sum of array
for n in nums:      # looping
    print(n)

nums.insert(1, 100) # insert middle
nums.remove(100)    # remove middle
print(100 in nums)  # search

import heapq
heapq.heapify(nums) # build heap

# sometimes even nested loops can be O(n)
# (e.g. monotonic stack or sliding window)

# Traverse a square grid
nums = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
for i in range(len(nums)):
    for j in range(len(nums[i])): 
        print(nums[i][j])


# Get every pair of elements in array
nums = [1, 2, 3]
for i in range(len(nums)):
    for j in range(i + 1, len(nums)):
        print(nums[i], nums[j])

# Insertion sort (insert in middle n times -> n^2)

# Get every pair of elements from two arrays
nums1, nums2 = [1, 2, 3], [4, 5]
for i in range(len(nums1)):
    for j in range(len(nums2)):
        print(nums1[i], nums2[j])

# Traverse rectangle grid
nums = [[1, 2, 3], [4, 5, 6]]
for i in range(len(nums)):
    for j in range(len(nums[i])):
        print(nums[i][j])

# Get every triplet of elements in array
nums = [1, 2, 3]
for i in range(len(nums)):
    for j in range(i + 1, len(nums)):
        for k in range(j + 1, len(nums)):
            print(nums[i], nums[j], nums[k])

# Binary search
nums = [1, 2, 3, 4, 5]
target = 6
l, r = 0, len(nums) - 1
while l <= r:
    m = (l + r) // 2
    if target < nums[m]:
        r = m - 1
    elif target > nums[m]:
        l = m + 1
    else:
        print(m)
        break

# Binary Search on BST
def search(root, target):
    if not root:
        return False
    if target < root.val:
        return search(root.left, target)
    elif target > root.val:
        return search(root.right, target)
    else: 
        return True

# Heap Push and Pop
import heapq
minHeap = []
heapq.heappush(minHeap, 5)
heapq.heappop(minHeap)

# HeapSort
import heapq
nums = [1, 2, 3, 4, 5]
heapq.heapify(nums)     # O(n)
while nums:
    heapq.heappop(nums) # O(logn)

# MergeSort (and most built-in sorting functions)

# Recursion, tree height n, two branches
def recursion(i, nums):
    if i == len(nums):
        return 0
    branch1 = recursion(i + 1, nums)
    branch2 = recursion(i + 2, nums)

# c branches, where c is sometimes n.
def recursion(i, nums, c):
    if i == len(nums):
        return 0
    
    for j in range(i, i + c):
        branch = recursion(j + 1, nums)

# Get all factors of n
import math
n = 12
factors = set()
for i in range(1, int(math.sqrt(n)) + 1):
    if n % i == 0:
        factors.add(i)
        factors.add(n // i)

Conclusion:

With basic knowledge of of Python you could be able to understand the fundamentals of algorithms, with this examples to make your own conclusions.

You can find this code and more in my repo:

python-interview/big-o.ipynb at main · romdelaporte/python-interview

Feel free to fork ;)