What is Complexity Analysis?

• Complexity Analysis is the mathematical evaluation of the resources (time and memory) consumed by an algorithm.

• Think of it like ordering food at a restaurant:

🧠 Beginner Mental Model

• Bad waiter: Takes 5 minutes per person, so 100 people = 500 minutes. 😰 → $O(n)$ per group
• Good waiter: Takes a menu order once for the whole table → $O(1)$ per group
• The algorithm is the waiter. The input size $n$ is the number of people.

• Instead of measuring execution time in seconds (which varies across hardware, OS, and CPU load), we measure complexity in terms of the number of basic operations and memory slots used relative to input size $n$.
• We express this using asymptotic notations to describe the growth rate of resource usage as input size scales toward infinity.

Key Terms

Why It Matters

• Hardware improvements (faster CPUs, more RAM) cannot fix a fundamentally inefficient algorithm. As data scales, algorithmic efficiency dominates hardware performance.

• Scaling Breakdown $10^9$ operations per second. Here is how different algorithms scale for input size $n=10^6$ (one million elements):

  Suppose a computer can perform

  • Logarithmic time $O(\log n)$ $\approx 20$ operations $⟹$ $0.02$ microseconds
  • Linear time $O(n)$ $=10^6$ operations $⟹$ $1$ millisecond
  • Linearithmic time $O(n\log n)$ $\approx 2\cdot 10^7$ operations $⟹$ $20$ milliseconds
  • Quadratic time $O(n^2)$ $=10^{12}$ operations $⟹$ $1,000$ seconds (~$16.6$ minutes)
  • Exponential time $O(2^n)$ $=2^{10^6}$ operations $⟹$ Will never finish (longer than the age of the universe)

  Choosing the correct algorithm can mean the difference between an instant response and a system crash.

📦 Real Analogy — Searching in a Phone Book

How It Works

1. Asymptotic Notations

• We use three primary mathematical notations to describe the bounds of an algorithm:

• When do we use which?

  • In interviews and practice, people almost always say “Big O” even when they technically mean Big Theta.
  • Big O = “ceiling” → useful to guarantee a worst case bound.
  • Big Omega = “floor” → useful to prove no algorithm can beat this limit.
  • Big Theta = “exact fit” → used in rigorous academic proofs.

• The definition $T(n)\le c\cdot g(n)$ for all $n\ge n_0$ means:

Formal Definition Explained (Beginner Friendly)

• We’re allowed to pick any positive constant $c$ (scaling factor).
• We’re allowed to ignore a finite “startup” region (i.e., for small $n$, the constants can dominate).
• Beyond some threshold $n_0$, $g(n)$ is always a valid upper bound on $T(n)$.
• In practice: constants are dropped because they vary by machine.

• Beyond $n_0$, the function $T(n)$ is sandwiched between $c_1\cdot g(n)$ and $c_2\cdot g(n)$.

Visualizing the Notations

T(n)
  |              ↑ c₂·g(n)  (upper bound, O)
  |            ↗
  |         ↗ T(n)           (actual runtime, inside Θ band)
  |       ↗
  |     ↗  ↗ c₁·g(n)        (lower bound, Ω)
  +------------------------→ n
       n₀

2. Simplification Rules

• When computing Big O, we apply these simplification rules:

• Constants don’t affect the growth rate: $O(2n)=O(n)$ $O(500)=O(1)$ $O(3n^2+7n)=O(n^2)$

Rule 1 — Drop Constants

• Keep only the fastest-growing term: $O(n^2+n)=O(n^2)\text{(because }{n}^2\gg n\text{ for large }n\text{)}$ $O(n+\log n)=O(n)$ $O(2^n+n^{100})=O(2^n)$

Rule 2 — Drop Non-Dominant Terms

• If two loops iterate over different inputs, use separate variables:

Rule 3 — Different Variables

def process(arr_a, arr_b):
    for a in arr_a:  # O(a)
        print(a)
    for b in arr_b:  # O(b)
        print(b)
# Total: O(a + b), NOT O(n)

Rule 4 — Sequences vs. Nesting

• Can you simplify these?

  1. $O(n+42)$ → ?
  2. $O(4n^3+2n^2+100n)$ → ?
  3. $O(n\cdot m+n)$ where $n\ne m$ → ?

  Answers: $O(n)$, $O(n^3)$, $O(n\cdot m)$

Quick Practice Problems

3. Common Complexity Classes

• Below are the most common complexity classes, ordered from fastest to slowest:

xychart-beta
    title "Growth Rate Curves (n vs Operations)"
    x-axis ["n=1", "n=2", "n=4", "n=8", "n=16"]
    y-axis "Operations" 0 --> 300
    line "O(1) Constant" [1, 1, 1, 1, 1]
    line "O(log n) Logarithmic" [0, 1, 2, 3, 4]
    line "O(n) Linear" [1, 2, 4, 8, 16]
    line "O(n log n) Linearithmic" [0, 2, 8, 24, 64]
    line "O(n^2) Quadratic" [1, 4, 16, 64, 256]

• The Complexity Ladder $O(1)<O(\log n)<O(\sqrt{n})<O(n)<O(n\log n)<O(n^2)<O(n^3)<O(2^n)<O(n!)$ Always aim as far left on this ladder as possible.

4. Mathematical Derivation of $O(\log n)$

• Logarithmic growth is incredibly efficient. Here is a step-by-step mathematical proof of why halving the search space (like in Binary Search) yields $O(\log n)$:
• 1. Let the initial search space size be $n$.
• 2. Each iteration divides the search space by $2$.
• 3. After $k$ iterations, the remaining size is: $\text{Size after }k\text{ steps}=\frac{n}{2^k}$
• 4. The search terminates when the space is reduced to $1$: $\frac{n}{2^k}=1⟹n=2^k$
• 5. Take the base-2 logarithm of both sides: ${\log }_2(n)={\log }_2(2^k)=k$
• 6. Therefore, the number of steps $k={\log }_2(n)$, which we write as $O(\log n)$.

• Logarithmic Growth Rule $n$ doubles, a logarithmic algorithm requires only one extra step.

  Every time the input size

  $n$	${\log }_2(n)$
  1	0
  2	1
  4	2
  8	3
  1,024	10
  1,048,576	20
  1,073,741,824 (1 billion)	30

• Since ${\log }_a(n)=\frac{{\log }_b(n)}{{\log }_b(a)}$ and ${\log }_b(a)$ is a constant, the bases only differ by a constant factor: $O({\log }_{2}n)=O({\log }_{10}n)=O(\log n)$ This is why we drop the base in Big O notation.

Why the base of log doesn’t matter in Big O

5. Code Complexity Analysis — Step by Step

• Here is how to identify complexities by reading code patterns:

• Operations that don’t depend on input size at all:

🟢 Constant Time — $O(1)$

def get_first_element(arr):
    # Always exactly 1 operation, regardless of len(arr)
    return arr[0] if arr else None
 
def is_even(n):
    # Single arithmetic check — constant time
    return n % 2 == 0
 
def swap(arr, i, j):
    # Three assignments — still O(1) since it's a fixed number
    arr[i], arr[j] = arr[j], arr[i]

• Each iteration cuts the problem in half (or by a constant fraction):

🟡 Logarithmic Time — $O(\log n)$

def binary_search(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      # Discard left half
        else:
            high = mid - 1     # Discard right half
    return -1
# Search space: n → n/2 → n/4 → ... → 1
# Steps = log₂(n)  →  O(log n)
 
def count_digits(n):
    count = 0
    while n > 0:
        n //= 10   # Divides by 10 each time
        count += 1
    return count
# Steps ≈ log₁₀(n)  →  O(log n)

• A single pass through all $n$ elements:

🟠 Linear Time — $O(n)$

def find_max(arr):
    max_val = arr[0]
    for item in arr:       # Loop runs n times
        if item > max_val:
            max_val = item
    return max_val
 
def sum_array(arr):
    total = 0
    for x in arr:          # One operation per element
        total += x
    return total

• A nested loop where both loops scale with $n$:

🔴 Quadratic Time — $O(n^2)$

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):           # Outer: n iterations
        for j in range(n - i - 1): # Inner: up to n iterations
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
# Total comparisons ≈ n*(n-1)/2  =  O(n²)
 
def print_all_pairs(arr):
    for i in range(len(arr)):    # O(n)
        for j in range(len(arr)): # O(n) for each i
            print(arr[i], arr[j])
# Total: O(n × n) = O(n²)

• Divide-and-conquer: split $\log n$ times, process $n$ elements each split:

🔵 Linearithmic Time — $O(n\log n)$

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])   # T(n/2) — split left half
    right = merge_sort(arr[mid:])  # T(n/2) — split right half
    return merge(left, right)      # O(n)   — merge step
 
def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result
# Recurrence: T(n) = 2T(n/2) + O(n) → O(n log n)

• Each call generates two more calls — the tree doubles at each level:

⚫ Exponential Time — $O(2^n)$

def fibonacci_naive(n):
    # For each call, we make 2 more recursive calls
    if n <= 1:
        return n
    return fibonacci_naive(n - 1) + fibonacci_naive(n - 2)
# Call tree has ~2^n nodes → O(2^n) time, O(n) space
 
def all_subsets(arr):
    # Generates all 2^n subsets of arr
    if not arr:
        return [[]]
    first = arr[0]
    rest_subsets = all_subsets(arr[1:])
    return rest_subsets + [[first] + s for s in rest_subsets]

• Not all nested loops are $O(n^2)$. Always trace the actual iterations:

🟣 Tricky Multi-Loop Example

def mystery(n):
    i = 1
    while i < n:
        i *= 2   # i doubles: 1, 2, 4, 8, ..., n
    # Loop runs log₂(n) times → O(log n) ❗ NOT O(n)
 
def print_triangle(n):
    for i in range(n):           # n rows
        for j in range(i + 1):   # 1, 2, 3, ..., n iterations
            print("*", end=" ")
    # Total = 1 + 2 + ... + n = n(n+1)/2 = O(n²)

6. Recurrence Relations & Master Theorem

• For recursive divide-and-conquer algorithms, we express time complexity as a recurrence relation: $T(n)=aT(n/b)+f(n)$
• Where:
  • $a\ge 1$: Number of subproblems at each recursion level.
  • $b>1$: Factor by which the input size shrinks.
  • $f(n)$: Work done outside the recursive calls (splitting, merging, processing).

• For merge_sort: T(n) = 2T(n/2) + O(n)

Step-by-Step: Reading a Recurrence

• The Master Theorem provides a shortcut to solve recurrences of this form:

• The 3 Cases of the Master Theorem critical exponent: $p={\log }_{b}a$

  First compute the

  Case 1 — Recursive work dominates (subproblems take most time): $\text{If }f(n)=O(n^{p-ϵ})\text{ for some }ϵ>0,\text{ then:}$ $T(n)=\Theta (n^p)$

  Case 2 — Work is balanced (split cost equals recursive cost): $\text{If }f(n)=\Theta (n^p),\text{ then:}$ $T(n)=\Theta (n^p\log n)$

  Case 3 — Combining work dominates (merge/split takes most time): $\text{If }f(n)=\Omega (n^{p+ϵ})\text{ for some }ϵ>0,\text{ then:}$ $T(n)=\Theta (f(n))$

Real-World Recurrence Examples

• Binary Search: $T(n)=T(n/2)+O(1)$
  • $a=1$, $b=2$, $f(n)=O(1)$
  • Critical exponent: $p={\log }_{2}1=0$, so $n^p=1$
  • $f(n)=O(1)=\Theta (n^0)$ → Case 2
  • $T(n)=\Theta (1\cdot \log n)=\Theta (\log n)✅$
• Merge Sort: $T(n)=2T(n/2)+O(n)$
  • $a=2$, $b=2$, $f(n)=O(n)$
  • Critical exponent: $p={\log }_{2}2=1$, so $n^p=n$
  • $f(n)=O(n)=\Theta (n^1)$ → Case 2
  • $T(n)=\Theta (n\log n)✅$
• Strassen’s Matrix Multiply: $T(n)=7T(n/2)+O(n^2)$
  • $a=7$, $b=2$, $f(n)=O(n^2)$
  • Critical exponent: $p={\log }_{2}7\approx 2.807$
  • $f(n)=O(n^2)=O(n^{2.807-0.807})$ → Case 1
  • $T(n)=\Theta (n^{{\log }_{2}7})\approx \Theta (n^{2.807})✅$

• For $T(n)=2T(n/2)+n$:

Recursion Tree Method (Alternative to Master Theorem)

Level 0:        n                     → cost: n
Level 1:    n/2   n/2                 → cost: n
Level 2:  n/4 n/4 n/4 n/4             → cost: n
...
Level k:  [2^k nodes, each n/2^k]     → cost: n
                                        (log n levels)
Total cost = n × log n = O(n log n)

7. Space Complexity & the Call Stack

• Space complexity measures the memory an algorithm uses relative to input size $n$.

• Interview Convention auxiliary space when they say "space complexity". We generally exclude the input itself.

  Most algorithm interviews refer to

• When a function calls itself recursively, each active call occupies a stack frame on the call stack:

Call Stack Memory

Call Stack for: factorial(4)
┌─────────────────────┐
│  factorial(1) → 1   │  ← Top of stack (most recent)
├─────────────────────┤
│  factorial(2)        │
├─────────────────────┤
│  factorial(3)        │
├─────────────────────┤
│  factorial(4)        │  ← Bottom of stack (first call)
└─────────────────────┘
Depth = 4 = n  →  Space: O(n)

Space Complexity Examples

# O(1) Space — Iterative: single stack frame, fixed variables
def sum_iterative(n):
    total = 0
    for i in range(1, n + 1):
        total += i
    return total
 
# O(n) Space — Recursive: n stack frames deep
def sum_recursive(n):
    if n == 0:
        return 0
    return n + sum_recursive(n - 1)
 
# O(log n) Space — Recursive Binary Search: log n stack frames
def binary_search_recursive(arr, low, high, target):
    if low > high:
        return -1
    mid = (low + high) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, mid + 1, high, target)
    else:
        return binary_search_recursive(arr, low, mid - 1, target)
 
# O(n) Space — Creating a new array
def double_array(arr):
    return [x * 2 for x in arr]  # New list of size n

Iterative vs Recursive Space

8. Amortized Analysis

• Some operations are expensive occasionally but cheap most of the time. Amortized Analysis averages the cost per operation across a long sequence to give a tighter bound than worst-case alone.

• When inserting elements into a dynamic array:

Example: Dynamic Array (Python list / C++ std::vector)

1. Normal insert (space available): $O(1)$ — just write to empty slot.
2. Full array insert (no space): Allocate $2n$ slots, copy all $n$ elements, then insert → $O(n)$ one-time cost.
3. After doubling, the next $n$ inserts are all $O(1)$ again.

• Amortized Cost: $\text{Total cost of }n\text{ insertions}=\underset{\text{Normal inserts}}{\underbrace{n\cdot O(1)}}+\underset{\text{Doubling cost}}{\underbrace{O(n)}}=O(n)$ $\text{Amortized cost per insertion}=\frac{O(n)}{n}=\mathbf{O}(1)$

• Banker's Argument $O(1)$ insert as paying 2 coins:

  Think of each

  • 1 coin for itself
  • 1 coin saved in a “doubling bank”

  When doubling happens, you have $n$ coins saved → can afford the $O(n)$ copy. Every insert’s amortized cost = 2 coins = $O(1)$.

Other Amortized Examples

9. Best / Average / Worst Case — When Do They Differ?

• Complexity can vary depending on the specific input. A complete analysis covers all three cases:

def linear_search(arr, target):
    for i, item in enumerate(arr):
        if item == target:
            return i    # Best case: O(1) if target is at index 0
    return -1           # Worst case: O(n) if not found

• Quick Sort and Pivot Selection $O(n^2)$ of Quick Sort occurs when the pivot always splits the array into $[n-1,0]$ (e.g., always picking the smallest element on a sorted array). Randomized Quick Sort avoids this by choosing pivots randomly → expected $O(n\log n)$.

  The worst case

Real-World Applications

• Databases store millions of rows. A full-table scan without an index is $O(n)$. Adding a B-Tree index transforms lookups to $O(\log n)$.

🗄️ Database Indexing

• Searching 1 million rows without index: ~$1,000,000$ comparisons
• Searching with B-Tree index: ~$20$ comparisons (${\log }_{2}10^6\approx 20$)

• Trade brokers use hash maps ($O(1)$ amortized lookup) instead of balanced BSTs ($O(\log n)$) to minimize microsecond-scale latency. At 10,000 trades/second, even $O(\log n)$ can be a bottleneck.

⚡ High-Frequency Trading (HFT)

• Network routers handle millions of packets/second. They use Trie structures for prefix matching IP addresses in $O(L)$ time (where $L=32$ bits for IPv4), completely independent of total number of routes $n$.

🌐 Network Routing

• The security of RSA encryption relies on the fact that multiplying two large primes is $O(n^2)$ but factoring the product back is believed to be exponential — the computational gap is the security guarantee.

🔒 Cryptography

• DNA sequence alignment uses Dynamic Programming algorithms like Smith-Waterman in $O(n\cdot m)$ time. For whole-genome alignment (billions of bases), approximations and heuristics reduce this to $O(n\log n)$.

🧬 Bioinformatics

Key Takeaways

• Time & Space — Analyze operations performed (time) and extra memory allocated (space). Both matter.
• Big O is the Standard — In practice, Big O (worst case) is what engineers discuss. It’s the safety guarantee.
• Simplify ruthlessly — Drop constants and non-dominant terms. $O(3n^2+50n+200)=O(n^2)$.
• Logarithmic is powerful — $O(\log n)$ means doubling the input only costs 1 more step. Always prefer it over $O(n)$ when possible.
• Recursion has hidden costs — Every recursive call adds a stack frame. A $k$-level-deep recursion costs $O(k)$ space.
• Amortized smooths spikes — When one expensive operation enables many cheap ones, the true per-operation cost is lower than it looks.
• Context matters — $O(n^2)$ is fine for $n=100$; catastrophic for $n=10^6$. Always estimate the expected input size.

graph TD
  A["Input: n"] --> B{"What does the algorithm do?"}
  B -->|"Fixed ops regardless of n"| C["O(1) — Constant"]
  B -->|"Halves problem each step"| D["O(log n) — Logarithmic"]
  B -->|"One pass through all n"| E["O(n) — Linear"]
  B -->|"Divide + merge each level"| F["O(n log n) — Linearithmic"]
  B -->|"Nested loop over n"| G["O(n²) — Quadratic"]
  B -->|"Two branches per call"| H["O(2^n) — Exponential"]

More Learn

• • Big-O Cheat Sheet — Quick reference for all complexity classes with data structures
• • Khan Academy: Asymptotic Notation — Thorough introduction to algorithm math
• • Master Theorem - Wikipedia — In-depth proof and edge cases
• • Visualgo — Algorithm Visualizer — Interactive visual animations for sorting and searching
• • MIT OpenCourseWare — Introduction to Algorithms — Full lecture series with problem sets