title: "Big O Analysis Master Sheet" description: "Complete reference for asymptotic notation, complexity analysis techniques, and time/space complexity bounds for algorithms and data structures." category: "algorithm-analysis" difficulty: "intermediate" tags: ["big-o", "complexity", "asymptotic-notation", "algorithm-analysis", "time-complexity", "space-complexity"] estimatedTime: "25 minutes" lastUpdated: "2025-01-10"

Enhanced SEO fields

seo_title: "Big O Analysis Cheat Sheet: Complete Guide to Algorithm Complexity" seo_description: "Master algorithm complexity analysis with this comprehensive Big O notation reference. Includes time/space complexity tables, Master Theorem examples, and practical analysis techniques." seo_keywords: ["big o analysis cheat sheet", "algorithm complexity guide", "time complexity reference", "space complexity analysis", "asymptotic notation tutorial", "master theorem examples", "algorithm performance analysis"] canonical_url: "https://clelandco.com/cheat-sheets/algorithm-analysis/big-o-analysis" cover_image: "/images/cheat-sheets/algorithm-analysis/big-o-cover.jpg" target_audience: "Computer Science Students, Software Engineers, Technical Interviews" content_type: "reference-guide" prerequisites: ["Basic algorithms knowledge", "Mathematical notation familiarity"]

Big O Analysis Master Sheet

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

Quick Reference Table

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)$:

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

Trees

Hash Tables

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

Sorting Algorithm Complexities

Graph Algorithm Complexities

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

1. Drop constants: $O(2n) = O(n)$
2. Drop lower-order terms: $O(n^2 + n) = O(n^2)$
3. Different inputs use different variables: $O(a + b)$ not $O(n)$
4. Nested loops multiply: $O(n) \times O(m) = O(nm)$
5. 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

1. Always clarify: What are we optimizing for? Time or space?
2. State assumptions: Input size, data distribution, constraints
3. Analyze all cases: Best, average, worst
4. Consider trade-offs: Time vs space complexity
5. 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!