Big O Analysis Cheat Sheet: Complete Guide to Algorithm Complexity

Master asymptotic notation and complexity analysis with this comprehensive reference guide.

Quick Reference Table

Notation	Name	Definition	Example
$O(f(n))$	Big O	Upper bound	$O(n^2)$
$\Omega(f(n))$	Big Omega	Lower bound	$\Omega(n \log n)$
$\Theta(f(n))$	Big Theta	Tight bound	$\Theta(n)$
$o(f(n))$	Little o	Strict upper bound	$o(n^2)$
$\omega(f(n))$	Little omega	Strict lower bound	$\omega(n)$

Common Complexity Classes

Time Complexities (Best to Worst)

O(1)        - Constant
O(log n)    - Logarithmic
O(n)        - Linear
O(n log n)  - Linearithmic
O(n²)       - Quadratic
O(n³)       - Cubic
O(2^n)      - Exponential
O(n!)       - Factorial

Growth Rate Comparison

For large n, the following inequality holds: $O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)$

Big O Notation Deep Dive

Definition

$f(n) = O(g(n))$ if there exist positive constants $c$ and $n_0$ such that: $0 \leq f(n) \leq c \cdot g(n) \text{ for all } n \geq n_0$

Key Properties

Transitivity: If $f = O(g)$ and $g = O(h)$ , then $f = O(h)$
Scaling: $O(c \cdot f(n)) = O(f(n))$ for any constant $c > 0$
Addition: $O(f(n) + g(n)) = O(\max(f(n), g(n)))$
Multiplication: $O(f(n) \cdot g(n)) = O(f(n)) \cdot O(g(n))$

Algorithm Analysis Techniques

1. Counting Operations

def linear_search(arr, target):
    for i in range(len(arr)):      # O(n) iterations
        if arr[i] == target:       # O(1) comparison
            return i               # O(1) return
    return -1                      # O(1) return
# Total: O(n)

2. Recurrence Relations

Master Theorem: For recurrences of the form $T(n) = aT(n/b) + f(n)$ :

Case	Condition	Solution
1	$f(n) = O(n^c)$ where $c < \log_b a$	$T(n) = \Theta(n^{\log_b a})$
2	$f(n) = \Theta(n^c \log^k n)$ where $c = \log_b a$	$T(n) = \Theta(n^c \log^{k+1} n)$
3	$f(n) = \Omega(n^c)$ where $c > \log_b a$	$T(n) = \Theta(f(n))$

Example: Merge Sort

$T(n) = 2T(n/2) + O(n)$
$a = 2, b = 2, f(n) = O(n)$
$\log_2 2 = 1$ , so Case 2 applies
$T(n) = \Theta(n \log n)$

3. Loop Analysis

Nested Loops:

for i in range(n):           # O(n)
    for j in range(n):       # O(n) for each i
        # O(1) operation
# Total: O(n²)

Dependent Loops:

for i in range(n):           # O(n)
    for j in range(i):       # O(i) for each i
        # O(1) operation
# Total: O(1 + 2 + ... + n) = O(n²)

Data Structure Complexities

Arrays and Lists

Operation	Array	Dynamic Array	Linked List
Access	$O(1)$	$O(1)$	$O(n)$
Search	$O(n)$	$O(n)$	$O(n)$
Insertion	$O(n)$	$O(1)$ amortized	$O(1)$
Deletion	$O(n)$	$O(n)$	$O(1)$

Trees

Tree Type	Search	Insert	Delete	Notes
Binary Search Tree	$O(h)$	$O(h)$	$O(h)$	$h$ can be $O(n)$ worst case
AVL Tree	$O(\log n)$	$O(\log n)$	$O(\log n)$	Self-balancing
Red-Black Tree	$O(\log n)$	$O(\log n)$	$O(\log n)$	Self-balancing
B-Tree	$O(\log n)$	$O(\log n)$	$O(\log n)$	Optimized for disk I/O

Hash Tables

Operation	Average	Worst Case
Search	$O(1)$	$O(n)$
Insert	$O(1)$	$O(n)$
Delete	$O(1)$	$O(n)$

Load Factor: $\alpha = \frac{n}{m}$ where $n$ = elements, $m$ = table size

Sorting Algorithm Complexities

Algorithm	Best Case	Average Case	Worst Case	Space	Stable
Bubble Sort	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	Yes
Selection Sort	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	No
Insertion Sort	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	Yes
Merge Sort	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	$O(n)$	Yes
Quick Sort	$O(n \log n)$	$O(n \log n)$	$O(n^2)$	$O(\log n)$	No
Heap Sort	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	$O(1)$	No

Graph Algorithm Complexities

Algorithm	Time Complexity	Space Complexity	Use Case
BFS	$O(V + E)$	$O(V)$	Shortest path (unweighted)
DFS	$O(V + E)$	$O(V)$	Topological sort, cycles
Dijkstra	$O((V + E) \log V)$	$O(V)$	Shortest path (weighted)
Floyd-Warshall	$O(V^3)$	$O(V^2)$	All-pairs shortest path
Kruskal's MST	$O(E \log E)$	$O(V)$	Minimum spanning tree
Prim's MST	$O(E \log V)$	$O(V)$	Minimum spanning tree

Space Complexity Analysis

Stack Space in Recursion

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)
# Space: O(n) due to call stack

Auxiliary Space vs Total Space

Auxiliary Space: Extra space used by algorithm
Total Space: Auxiliary space + input space

Common Space Patterns

In-place algorithms: $O(1)$ extra space
Recursive algorithms: $O(h)$ where $h$ is recursion depth
Dynamic programming: Often $O(n)$ or $O(n^2)$ for memoization

Analysis Cheat Sheet

Quick Rules

Drop constants: $O(2n) = O(n)$
Drop lower-order terms: $O(n^2 + n) = O(n^2)$
Different inputs use different variables: $O(a + b)$ not $O(n)$
Nested loops multiply: $O(n) \times O(m) = O(nm)$
Consecutive loops add: $O(n) + O(m) = O(n + m)$

Common Pitfalls

Confusing average vs worst case
Ignoring space complexity
Not considering different input sizes
Assuming best-case scenarios

Interview Tips

Always clarify: What are we optimizing for? Time or space?
State assumptions: Input size, data distribution, constraints
Analyze all cases: Best, average, worst
Consider trade-offs: Time vs space complexity
Verify with examples: Test your analysis with small inputs

Practical Examples

Example 1: Two Sum

def two_sum_naive(nums, target):
    for i in range(len(nums)):           # O(n)
        for j in range(i+1, len(nums)):  # O(n)
            if nums[i] + nums[j] == target:
                return [i, j]
    return []
# Time: O(n²), Space: O(1)

def two_sum_optimal(nums, target):
    seen = {}                            # O(n) space
    for i, num in enumerate(nums):       # O(n) time
        complement = target - num
        if complement in seen:           # O(1) average
            return [seen[complement], i]
        seen[num] = i                    # O(1) average
    return []
# Time: O(n), Space: O(n)

Example 2: Finding Duplicates

def has_duplicate_sort(nums):
    nums.sort()                     # O(n log n)
    for i in range(1, len(nums)):   # O(n)
        if nums[i] == nums[i-1]:
            return True
    return False
# Time: O(n log n), Space: O(1)

def has_duplicate_set(nums):
    seen = set()                    # O(n) space
    for num in nums:                # O(n) time
        if num in seen:             # O(1) average
            return True
        seen.add(num)               # O(1) average
    return False
# Time: O(n), Space: O(n)

Mathematical Foundations

Logarithm Properties

$\log_2 n$ - Binary logarithm (common in CS)
$\log(ab) = \log a + \log b$
$\log(a^k) = k \log a$
$\log_2 n = O(\log n)$ - Base doesn't matter for Big O

Summation Formulas

$\sum_{i=1}^{n} i = \frac{n(n+1)}{2} = O(n^2)$
$\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6} = O(n^3)$
$\sum_{i=0}^{n} 2^i = 2^{n+1} - 1 = O(2^n)$

Quick Reference Summary

Remember: Big O analysis helps us understand how algorithms scale. Focus on the growth rate for large inputs, not exact operation counts.

Golden Rule: When in doubt, trace through your algorithm with increasing input sizes and observe the pattern!