Foundations

Algorithm Analysis

● Beginner ⏱ 8 min read dsa

Big O describes the upper bound on growth, but real algorithms behave differently depending on the input. Algorithm analysis examines how an algorithm performs across all possible inputs — not just the worst scenario.

Best, Average & Worst Case

For any algorithm, three complexity scenarios exist:

Case	Notation	Meaning
Best	Ω(f(n))	Lower bound — the minimum work the algorithm does
Average	Θ(f(n))	Expected work over all possible inputs of size n
Worst	O(f(n))	Upper bound — the maximum work for any input

Python

def linear_search(arr, target):
    for i, val in enumerate(arr):
        if val == target:
            return i       # found early → best case O(1)
    return -1
    # Best case:    target is arr[0]             → O(1)
    # Average case: target is somewhere in arr   → O(n/2) = O(n)
    # Worst case:   target not in arr            → O(n)

💡

Which case matters?

In interviews and documentation, “O(n)” without qualification means worst case. When comparing algorithms, always compare the same case (worst vs worst, average vs average).

Loop Analysis

The most reliable way to determine complexity is to count iterations systematically.

Python

# Rule 1: Single loop → O(n)
for i in range(n):          # n iterations
    do_work(i)              # O(1) each → total O(n)

# Rule 2: Loop with halving → O(log n)
i = n
while i > 1:
    i = i // 2              # halves each step → O(log n) iterations

# Rule 3: Two sequential loops → O(n) + O(n) = O(n)
for i in range(n):          # n iterations
    process_a(i)
for j in range(n):          # n iterations
    process_b(j)
# Drop constants: O(2n) = O(n)

Nested Loops

Nested loops multiply their iteration counts.

Python

# Nested loops → O(n²)
for i in range(n):           # n iterations
    for j in range(n):       # n iterations each
        print(i, j)          # n × n = O(n²)

# Triangular nested loop → still O(n²) (half of n²)
for i in range(n):
    for j in range(i + 1, n):   # approximately n²/2 iterations
        print(i, j)             # drop constant → O(n²)

# Loop with log inner → O(n log n)
for i in range(n):           # n iterations
    j = 1
    while j < n:             # log n iterations
        j *= 2
# Total: n × log n = O(n log n)

Comparing Algorithms

Two algorithms for the same problem can have identical Big O but very different real-world performance. Always consider constants and the expected input size.

Python

# Both find sum of a list — both O(n), but implementation differs

# Approach A: explicit loop
def sum_loop(arr):
    total = 0
    for x in arr:
        total += x
    return total

# Approach B: built-in (optimised C under the hood)
def sum_builtin(arr):
    return sum(arr)

# Same Big O, but sum() is ~5x faster in CPython due to C implementation.
# Big O predicts growth rate, not absolute speed.

⚠️

Small n: constants win

For n < 50, an O(n²) algorithm with a tiny constant often beats O(n log n) in practice. Python's sorted() uses Timsort, which falls back to insertion sort (O(n²)) for small subarrays for exactly this reason.

Amortized Analysis

Some operations are occasionally expensive but cheap on average. Amortized analysis spreads the cost of rare expensive operations over many cheap ones.

Python

# Python list.append() — amortized O(1)
# Occasionally triggers a resize (copies all elements → O(n))
# but this happens so rarely that the average cost per append is O(1)

arr = []
for i in range(1000):
    arr.append(i)   # 1000 appends — maybe 10 resizes of increasing cost
                    # Total work ≈ 2000 steps → amortized O(1) per append

# The key insight: after a resize to size k, the next k appends are O(1)
# before the next resize. Total cost = O(n) for n appends → O(1) each.