Intro to Big O Notation

Note: A more detailed dive on the topic can be found in my old site’s blog 1k2s.netlify.app. This page goes over the same topic but in a more succinct matter.

Big $O$ Notation is a mathematical notation that describes the behavior of a value (most commonly denoted as $n$ as it reaches infinity. Although well defined as such in math, applied in programming it comes in 2 forms Time Complexity and Space Complexity.

Dictionary

1. Time Complexity: Used to determine how much time it takes for the CPU to run the code.
2. Space Complexity: Memory resources needed to complete the algorithm.
3. Compile Time: This is not measured with Big O, instead we care about runtime, and even though some algorithms can be optimized from $O(n)$ to $O(1)$ (like Gauss Sum for example, this blog doesn’t go over these kinds of optimizations.
4. Runtime: When the program is actually executed. This is what LeetCode and other platforms alike measure.

Analysis

Below are the most common algorithm complexities listed, in general it’s important to know that when assessing an algorithm’s complexity, we omit all constants and instead focus on how the algorithm works as the input increases in size.

$O(1)$ - Constant Complexity

Seen in:

• Pushing an item to the back of a Vector.
• Looking up an item in a Hash Map/Set.
• Getting the first element of a Linked List.

$O(\log n)$ - Logarithmic Complexity

The concept is as follows: if you divide the amount of steps required by $k$ (most of the time $k=2$) on every iteration, then your algorithm’s time complexity is $O(\log n)$.

Primary use is Binary Search. It is the gold standard for searching sorted data sets.

$O(n)$ - Linear Complexity

Described as doing at least one full iteration on your data.

Note: A common trick question is removing the first item of a Vector is $O(n)$, unlike removing the last one which is $O(1)$. This is due to how Vectors are structured in memory and how every subsequent item needs to be moved forward whenever you remove at the first place.

$O(n\log n)$ - Linearithmic Complexity

Usually where efficient sorting algorithms fall: Quicksort, Heapsort, and Merge sort, all in regards to time complexity.

$O(n^2)$ - Quadratic Complexity

Commonly seen in nested loops or matrix traversals (arr[i][j]). Bubble Sort also falls here.

Note: Often $O(n^2)$ solutions are referred to as Brute Force. A common approach to optimizing such problems is called Dynamic Programming.

Complexity Table

In for easy reference you could refer to it:

Code Implementation Examples

import math

# O(1) - Constant Time
# No matter how large the input 'arr' is, this takes one step.
def constant_example(arr):
    return arr[0] if arr else None

# O(log n) - Logarithmic Time
# Binary Search: Cutting the search area in half each iteration.
def logarithmic_example(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

# O(n) - Linear Time
# A single loop that visits every element once.
def linear_example(arr):
    for item in arr:
        print(item)

# O(n log n) - Linearithmic Time
# Typical for efficient sorts like Merge Sort.
def linearithmic_example(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = linearithmic_example(arr[:mid])
    right = linearithmic_example(arr[mid:])
    return sorted(left + right) # Simplified merge step

# O(n^2) - Quadratic Time
# Nested loops where we compare every element to every other element.
def quadratic_example(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n):
            print(f"Comparing {arr[i]} and {arr[j]}")

# O(sqrt(n)) - Sublinear Time
# Trial division for primality testing.
def sqrt_n_example(n):
    if n < 2: return False
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

Optimizing for Memory vs. Space

Below is a video with a very comprehensive showcase of all three approaces: Trial Division, Sieve of Eratosthenes, and Dijkstra’s Approach.

1. Trial Division

The most memory-efficient but slowest method. It relies on the fact that divisors are mirrored around the square root of $n$.

• Time: $O(\sqrt{n})$ <<= on theory, good, in reality the slowness is due to Integer Factorization.
• Space: $O(1)$

2. Sieve of Eratosthenes

The quickest for bulk evaluation.

• Time: $O(n\log \log n)$
• Space: $O(n)$ (requires a boolean array up to $n$)

3. Dijkstra’s Approach

A balanced approach using a “pool” of tuples to track multiples, avoiding the massive memory hit of the Sieve while staying faster than Trial Division.

• Time: $O(n\log \log n)$ <<= whilst sharing the same time complexity as Sieve of Eratosthenes, it usually performs slower due to Cache Locality.
• Space: $O(n)$ (requires a boolean array up to $n$)

Not only Big $O$

Big $O$ describes the worst-case scenario. Mathematically:

Big Omega ($\Omega$)

Describes the best-case scenario (lower bound):

Big Theta ($\Theta$)

Describes the tightest bound (average case):

Summary

• Big $O$ is like $\le$ (Worst case / Upper bound)
• Big $\Omega$ is like $\ge$ (Best case / Lower bound)
• Big $\Theta$ is like $==$ (Tightly bounded / Average case)

Determining what to optimize depends on your specific use case. A big factor to these algorithms is also input size, sometimes algorithms like bubble sort outperform ones like quicksort due to better cache locality (and aggressive compiler optimization because it’s a more predictable pattern) on small input sizes.