Big-O Cheat Sheet: Time and Space Complexity Guide

Big-O Cheat Sheet

Complete guide to time and space complexity for technical interviews

What is Big-O Notation?

Big-O notation describes the worst-case performance of an algorithm as the input size grows. It helps compare algorithm efficiency and is crucial for technical interviews.

Key Principle:

Big-O describes the growth rate, not exact runtime. We care about behavior as n → ∞.

Common Time Complexities (Ranked)

Big-O Name Example n=10 n=100 n=1000
O(1) Constant Array access, hash lookup 1 1 1
O(log n) Logarithmic Binary search, balanced tree 3 7 10
O(n) Linear Linear search, array traversal 10 100 1,000
O(n log n) Linearithmic Merge sort, quicksort (avg) 30 664 9,966
O(n²) Quadratic Bubble sort, nested loops 100 10,000 1,000,000
O(n³) Cubic Triple nested loops 1,000 1,000,000 1,000,000,000
O(2^n) Exponential Fibonacci recursion, subsets 1,024 1.27×10³⁰ ∞ (impractical)
O(n!) Factorial Permutations, traveling salesman 3,628,800 ∞ ∞

Rule of Thumb for Interviews

  • n ≤ 10: O(n!) is acceptable
  • n ≤ 20: O(2^n) is acceptable
  • n ≤ 500: O(n³) is acceptable
  • n ≤ 5,000: O(n²) is acceptable
  • n ≤ 1,000,000: O(n log n) or better required
  • n > 1,000,000: O(n) or O(log n) required

Data Structure Operations

Array

  • Access: O(1)
  • Search: O(n)
  • Insert (end): O(1) amortized
  • Insert (beginning): O(n)
  • Delete: O(n)
  • Space: O(n)

Hash Table

  • Search: O(1) average, O(n) worst
  • Insert: O(1) average, O(n) worst
  • Delete: O(1) average, O(n) worst
  • Space: O(n)

Binary Search Tree (Balanced)

  • Search: O(log n)
  • Insert: O(log n)
  • Delete: O(log n)
  • Space: O(n)

Heap (Min/Max)

  • Find Min/Max: O(1)
  • Insert: O(log n)
  • Delete Min/Max: O(log n)
  • Build Heap: O(n)
  • Space: O(n)

Linked List

  • Access: O(n)
  • Search: O(n)
  • Insert (beginning): O(1)
  • Insert (end): O(n) or O(1) with tail pointer
  • Delete: O(n)
  • Space: O(n)

Sorting Algorithms

Algorithm Best Average Worst Space Stable?
Quick Sort O(n log n) O(n log n) O(n²) O(log n) No
Merge Sort O(n log n) O(n log n) O(n log n) O(n) Yes
Heap Sort O(n log n) O(n log n) O(n log n) O(1) No
Bubble Sort O(n) O(n²) O(n²) O(1) Yes
Insertion Sort O(n) O(n²) O(n²) O(1) Yes
Selection Sort O(n²) O(n²) O(n²) O(1) No

Calculating Big-O: Rules

1. Drop Constants

O(2n) → O(n)
O(500) → O(1)

2. Drop Lower Order Terms

O(n² + n) → O(n²)
O(n + log n) → O(n)

3. Different Inputs = Different Variables

for (int i = 0; i < a.length; i++) {  // O(a)
    for (int j = 0; j < b.length; j++) {  // O(b)
        ...
    }
}
// Time: O(a * b), NOT O(n²)

4. Amortized Analysis

Dynamic array append is O(1) amortized, even though occasional resize is O(n).

Space Complexity Rules

  • Recursion: O(depth) for call stack
  • Iteration: Usually O(1) unless creating new data
  • Memoization: Space = Time (usually)
  • In-place: O(1) extra space

Common Interview Pitfalls

Mistake: Assuming All Operations Are O(1)

  • str1 + str2 in most languages is O(n), not O(1)
  • list.contains() is O(n) for list, O(1) for set
  • list.remove(element) is O(n)

Mistake: Not Considering Space Complexity

An O(n) time, O(n) space solution may be worse than O(n log n) time, O(1) space for memory-constrained systems.

Mistake: Premature Optimization

Start with brute force, explain complexity, then optimize. Don’t jump to complex O(n) solution if O(n log n) is acceptable.

Quick Reference: When to Use What

  • Need fast lookup? → Hash Table (O(1))
  • Need sorted order? → BST (O(log n)) or sorted array with binary search
  • Need to find min/max quickly? → Heap (O(1) find, O(log n) insert/delete)
  • Need to track frequency? → Hash Map
  • Need sliding window? → Deque or Two Pointers
  • Need to try all possibilities? → Backtracking or DP

Practice Problems by Complexity

O(1) – Constant

  • Check if number is even/odd
  • Access array element by index
  • Swap two variables

O(log n) – Logarithmic

  • Binary search in sorted array
  • Find element in balanced BST
  • Power function (x^n) using fast exponentiation

O(n) – Linear

  • Find maximum in unsorted array
  • Check if array contains duplicates (with hash set)
  • Reverse a linked list

O(n log n) – Linearithmic

  • Merge sort, quicksort (average)
  • Find kth largest element (using heap)
  • Sort characters in a string

O(n²) – Quadratic

  • Find all pairs in array
  • Bubble sort, insertion sort
  • Check if one string is rotation of another (naive)

Interview Tips

  1. Always State Complexity: After explaining your approach, clearly state: “This solution is O(n) time and O(1) space.”
  2. Optimize When Asked: If interviewer asks “Can you do better?”, identify the bottleneck and optimize that part.
  3. Consider Trade-offs: Sometimes O(n) time with O(n) space is better than O(n²) time with O(1) space. Ask about constraints.
  4. Don’t Guess: If unsure, work through small examples to determine complexity.

Master Big-O notation to succeed in technical interviews!

Scroll to Top