Big-O Cheat Sheet: Time and Space Complexity of Data Structures and Algorithms

This Big O cheat sheet gives you the time and space complexity of common data structures, sorting algorithms and Java collections on one page, plus the reasoning you need to work out the complexity of code you have never seen before. The cheat-sheet tables are images you can save or share, and the same data is repeated as text under each one.

It is written for developers preparing for coding interviews and for anyone who wants Big O notation explained without the math-textbook detour. You will see how fast each complexity class grows at n = 10, 1,000 and 1,000,000, eight worked Java examples of how to calculate time complexity, amortized analysis using the real ArrayList growth rule from the JDK 25 source, and a "master theorem lite" for recursive code. Every program in this post was run on Java 25 and the output shown is real.

In this guide

• What Big-O notation means
• How fast each complexity grows (n = 10, 1,000, 1,000,000)
• How to calculate time complexity: rules and 8 worked Java examples
• Space complexity
• Amortized analysis: why ArrayList.add is O(1)
• Recursion complexity and the master theorem (lite)
• Cheat sheets: data structure operations, sorting algorithms, Java collections
• Common Big-O mistakes in interviews, plus an FAQ

What is Big-O notation?

Big-O notation describes how the running time (or memory) of an algorithm grows as the input size n grows. It keeps only the fastest-growing term and drops constant factors, so 3n² + 5n + 100 steps is simply O(n²). It answers "what happens when the input gets 10 times bigger?", not "how many milliseconds will this take?"

Dropping constants feels like cheating at first, but it is what makes Big-O useful. A machine twice as fast halves every constant; it does not change an O(n²) algorithm into an O(n) one. For large inputs, the growth rate decides which algorithm wins.

Best, average and worst case

The same algorithm can have different complexities for different inputs. Quicksort is O(n log n) on average but O(n²) when every pivot is a bad split. A hash table lookup is O(1) on average and O(n) in the worst case if everything collides. In interviews, "the complexity" means the worst case unless you say otherwise, and for hash-based structures people quote the average case and mention the worst.

Big-O vs Big-Theta vs Big-Omega

Formally, O(f) is an upper bound (grows no faster than f), Ω(f) is a lower bound (grows at least as fast as f), and Θ(f) is a tight bound (both). Binary search is O(n) in the strict sense, because log n grows no faster than n, but nobody would say that in an interview. In practice, "Big-O" is used to mean the tightest bound you can state, and that is how this cheat sheet uses it.

How fast does each complexity grow?

The chart shows the common complexity classes from fastest to slowest. The gap between them is small for tiny inputs and enormous for real ones.

Here is the same idea as numbers: the approximate number of steps each class needs for n = 10, 1,000 and 1,000,000. We printed this table with a short Java program (GrowthTable.java):

n          log2 n   n            n log2 n         n^2                  2^n
10         3.3      10           33               100                  1,024
1,000      10.0     1,000        9,966            1,000,000            a 302-digit number
1,000,000  19.9     1,000,000    19,931,569       1,000,000,000,000    a 301,030-digit number

Read it row by row. At n = 10, everything is fast. At n = 1,000, O(n²) is a million steps, which is still fine. At n = 1,000,000, O(n log n) is about 20 million steps (well under a second), while O(n²) is a trillion steps, which takes far too long for any interview problem or web request. O(2ⁿ) stops being usable somewhere in the 20s or 30s.

What input size can each complexity handle?

Problem constraints are a strong hint about the intended solution. A common rule of thumb from competitive programming assumes very roughly 10⁸ simple operations per second. It is only an estimate, since the real speed depends on the language, the machine and how heavy each step is, but it is good enough to rule approaches in or out:

• n ≤ 10-11: O(n!) is fine (all permutations)
• n ≤ 20-25: O(2ⁿ) is fine (all subsets, bitmask DP)
• n ≤ 500: O(n³)
• n ≤ 5,000-10,000: O(n²)
• n ≤ 10⁶: O(n log n) or O(n)
• n ≤ 10⁸: O(n) with a light loop body
• larger n: O(log n) or O(1), usually math or binary search

How to calculate time complexity

You do not need formal proofs. Look at the shape of the code, count how many times the innermost work runs as a function of n, and apply a handful of rules.

1. Count what grows with the input. Assignments, comparisons and arithmetic are O(1) each; what matters is how many times they repeat.
2. Sequential blocks add, then keep the biggest term. O(n) followed by O(n²) is O(n + n²) = O(n²).
3. Nested loops multiply. A loop of n inside a loop of n is O(n²); a loop of m inside a loop of n is O(n · m).
4. Halving or doubling gives a log. If the remaining work is cut in half each step, it takes about log₂ n steps.
5. Different inputs get different letters. Two lists of sizes n and m give O(n + m) or O(n · m), never O(n²).
6. Recursion: number of calls × work per call. Or write the recurrence and use the master theorem below.
7. Library calls are not free. list.contains, list.remove(0), substring and string concatenation hide an O(n) loop.

8 worked Java examples

Example 1: array access and HashMap lookup are O(1)

static int first(int[] a) {
    return a[0];
}

static int price(Map<String, Integer> prices, String sku) {
    return prices.getOrDefault(sku, 0);  // O(1) on average
}

Reading a[0] takes the same time whether the array has 5 or 5 million elements: the address is computed directly. HashMap.get hashes the key and jumps to one bucket, so it is O(1) on average. Constant time does not mean "fast", only "does not grow with n".

Example 2: one loop over the input is O(n)

static long sum(int[] a) {
    long total = 0;
    for (int x : a) total += x;
    return total;
}

The loop body runs once per element. Double the array and you double the work, which is the definition of linear time.

Example 3: two inputs, two loops is O(n + m)

static void printBoth(List<String> users, List<String> orders) {
    for (String u : users) System.out.println(u);    // n steps
    for (String o : orders) System.out.println(o);   // m steps
}

The loops run one after the other, so the costs add. Because the lists are different sizes, keep both variables: O(n + m). Writing O(n) would be wrong when there could be far more orders than users.

Example 4: checking every pair is O(n²)

static int countPairsWithSum(int[] a, int target) {
    int count = 0;
    for (int i = 0; i < a.length; i++)
        for (int j = i + 1; j < a.length; j++)
            if (a[i] + a[j] == target) count++;
    return count;
}

The inner loop runs n - 1 times, then n - 2, and so on down to 0. That totals n(n - 1) / 2, which is 499,500 for n = 1,000. Halving the work with j = i + 1 is a real speed-up, but it is a constant factor: the complexity is still O(n²). (With a HashMap of seen values, this exact problem drops to O(n).)

Example 5: binary search is O(log n)

static int binarySearch(int[] sorted, int key) {
    int lo = 0, hi = sorted.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (sorted[mid] == key) return mid;
        if (sorted[mid] < key) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

Each step throws away half of the remaining range. Starting from n elements, you can halve about log₂ n times before one element is left: 20 steps for a million elements, 30 for a billion. That is why "sorted input" in a problem statement should make you think of binary search.

Example 6: a loop around a doubling loop is O(n log n)

static long loopTimesDoubling(int n) {
    long steps = 0;
    for (int i = 0; i < n; i++)          // n times
        for (int j = 1; j < n; j *= 2)   // log2(n) times
            steps++;
    return steps;
}

The outer loop runs n times and the inner loop doubles j until it reaches n, about log₂ n times. Nested loops multiply: O(n log n). This is the same shape as merge sort, where each of log n levels does O(n) work.

Example 7: the harmonic loop is also O(n log n)

static long harmonic(int n) {
    long steps = 0;
    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j += i)  // n / i times
            steps++;
    return steps;
}

This one catches people out. It looks like O(n²), but the inner loop steps by i, so it runs n/1 + n/2 + n/3 + ... + n/n times. That is n times the harmonic series, which grows like the natural log of n, so the total is O(n log n). The Sieve of Eratosthenes and "for every number, visit its multiples" problems have this shape.

Example 8: recursive Fibonacci is exponential; memoized, it is O(n)

static long fib(int n) {
    return n < 2 ? n : fib(n - 1) + fib(n - 2);
}

static long fibMemo(int n, long[] memo) {
    if (n < 2) return n;
    if (memo[n] != 0) return memo[n];
    return memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
}

Each call makes two more calls, and the depth is n, so the call tree has up to 2ⁿ nodes: O(2ⁿ). (The tight bound is about 1.618ⁿ, the golden ratio, because the two branches have different depths, but O(2ⁿ) is the accepted interview answer.) With a memo array, each value from 2 to n is computed once, so the cost drops to O(n) time and O(n) space. That one change is the core idea of dynamic programming.

Check your answer by counting

When you are unsure, count the steps for n and 2n and look at the ratio. We instrumented the examples above with a step counter (OpCounts.java) and ran it:

example                   n = 1,000    n = 2,000    ratio
single loop                   1,000        2,000     2.00
all pairs i < j             499,500    1,999,000     4.00
halving                           9           10     1.11
loop x doubling              10,000       22,000     2.20
harmonic j += i               7,069       15,518     2.20

fibonacci calls              n = 20       n = 30    ratio
naive fib(n)                 21,891    2,692,537   123.00
memoized fib(n)                  39           59     1.51

Doubling n doubles O(n), quadruples O(n²), adds one step to O(log n), and slightly more than doubles O(n log n). For Fibonacci, adding just 10 to n multiplies the naive call count by 123, which is 1.618 to the power 10. The memoized version grows by 2 calls per extra n.

Hidden O(n) costs in Java code

Many slow solutions are not slow because of the loops you wrote, but because of a library call inside them:

// O(n^2): each += copies the whole string built so far
static String joinSlow(List<String> words) {
    String s = "";
    for (String w : words) s += w;
    return s;
}

// O(n): StringBuilder appends in amortized O(1) per character
static String joinFast(List<String> words) {
    StringBuilder sb = new StringBuilder();
    for (String w : words) sb.append(w);
    return sb.toString();
}

// O(n * m): List.contains scans the list every time
static List<Integer> commonSlow(List<Integer> a, List<Integer> b) {
    List<Integer> out = new ArrayList<>();
    for (Integer x : a) if (b.contains(x)) out.add(x);
    return out;
}

// O(n + m): build a HashSet once, then O(1) average lookups
static List<Integer> commonFast(List<Integer> a, List<Integer> b) {
    Set<Integer> inB = new HashSet<>(b);
    List<Integer> out = new ArrayList<>();
    for (Integer x : a) if (inB.contains(x)) out.add(x);
    return out;
}

Other common ones: ArrayList.remove(0) in a loop shifts every element each time (use ArrayDeque); LinkedList.get(i) inside a for loop walks the list from the nearer end on every call, which makes a simple loop O(n²); and String.substring copies the characters it returns, so it is O(k) for a substring of length k, not O(1).

Space complexity

Space complexity measures the extra memory an algorithm needs as n grows. Interviewers usually mean auxiliary space: memory beyond the input itself. Three things use it: new data structures you allocate, copies of the input, and the call stack of recursive functions.

static void reverseInPlace(int[] a) {     // O(1) extra space
    for (int i = 0, j = a.length - 1; i < j; i++, j--) {
        int t = a[i]; a[i] = a[j]; a[j] = t;
    }
}

static int[] reversedCopy(int[] a) {      // O(n) extra space
    int[] r = new int[a.length];
    for (int i = 0; i < a.length; i++) r[i] = a[a.length - 1 - i];
    return r;
}

static long sumRecursive(int[] a, int i) { // O(n) stack space: one frame per element
    return i == a.length ? 0 : a[i] + sumRecursive(a, i + 1);
}

The recursive sum looks like it uses no memory, but every call waits on the stack for the next one to return, so it needs n stack frames. Recursive binary search uses O(log n) stack, a recursive DFS on a tree uses O(height), and merge sort needs O(n) for its temporary array. Recursion that is n levels deep can also throw StackOverflowError in Java for large n; the JVM does not optimize away tail calls, so even tail-recursive code keeps every frame.

Time and space often trade against each other. The HashSet in commonFast spends O(m) memory to save O(n · m) time, and memoized Fibonacci spends O(n) memory to avoid exponential time. Say the trade-off out loud in an interview.

Amortized analysis: why ArrayList.add is O(1)

Amortized complexity is the average cost per operation over a long sequence of operations, even when a single operation is occasionally expensive. The classic example is ArrayList.add.

An ArrayList stores elements in an array. When the array is full, the next add allocates a bigger array and copies every element across, which is O(n) for that one call. In the JDK 25 source, the first add on a default ArrayList allocates 10 slots, and each later resize grows the capacity by half: newCapacity = oldCapacity + (oldCapacity >> 1). We replayed that exact rule for one million adds (AmortizedAdd.java):

adds: 1,000,000
resizes: 30
elements copied during resizes: 2,430,972
copies per add: 2.43
final capacity: 1,215,487

A million adds caused only 30 resizes and about 2.4 copies per add on average. Because the capacity grows geometrically, each resize happens after proportionally more cheap adds, and the total copying is a constant multiple of n. So n adds cost O(n), which is O(1) amortized per add. The ArrayList Javadoc states this directly: adding n elements requires O(n) time.

Two practical points follow. First, amortized O(1) is not the same as "every call is fast": one unlucky add still copies the whole array, which matters for latency-sensitive code. Second, if you know the final size, new ArrayList<>(expectedSize) skips the resizes entirely. The same reasoning explains why HashMap.put, ArrayDeque.offer and StringBuilder.append are amortized O(1): they all grow their backing array geometrically.

Recursion complexity and the master theorem (lite)

For divide-and-conquer code that splits the input into equal parts, write the running time as a recurrence:

T(n) = a · T(n / b) + O(n^d)

Here a is the number of recursive calls, n / b is the size of each subproblem, and O(n^d) is the work done outside the recursive calls (splitting and combining). Compare a with b^d:

• a < b^d: the top level dominates, T(n) = O(n^d).
• a = b^d: every level does the same work, T(n) = O(n^d log n).
• a > b^d: the leaves dominate, T(n) = O(n^(log_b a)).

Worked through on algorithms you know:

• Binary search: T(n) = T(n/2) + O(1). a = 1, b = 2, d = 0, so a = b^d → O(log n).
• Merge sort: T(n) = 2T(n/2) + O(n). a = 2, b = 2, d = 1, so a = b^d → O(n log n).
• Visiting every node of a balanced binary tree: T(n) = 2T(n/2) + O(1). a = 2 > b^d = 1 → O(n^(log₂ 2)) = O(n).
• Karatsuba multiplication: T(n) = 3T(n/2) + O(n). a = 3 > 2 → O(n^(log₂ 3)) ≈ O(n^1.585).
• Heavy combine step: T(n) = 2T(n/2) + O(n²). a = 2 < b^d = 4 → O(n²).

The master theorem does not cover recursion that shrinks the input by subtraction. For those, draw the recursion tree and multiply the number of calls by the work per call: T(n) = T(n - 1) + O(1) (recursive sum) is O(n); T(n) = T(n - 1) + O(n) (naive selection-style recursion) is O(n²); and T(n) = 2T(n - 1) + O(1) (two calls on n - 1, as in Tower of Hanoi) is O(2ⁿ). Naive Fibonacci, T(n) = T(n - 1) + T(n - 2) + O(1), does no more work than that, so O(2ⁿ) is a valid upper bound for it too. The general shortcut: number of calls × work per call, where a call tree with b branches per call and depth d has about b^d calls.

Big-O cheat sheet: data structure operations

Average case first; where the worst case is different, it follows after the slash.

• Array: access O(1), search O(n), insert O(n), delete O(n). Space O(n).
• Dynamic array (ArrayList): access O(1), search O(n), insert O(n), or O(1) amortized at the end, delete O(n), or O(1) at the end.
• Singly linked list: access O(n), search O(n), insert O(1) at the head, delete O(1) at the head (O(n) to find any other node).
• Doubly linked list: access O(n), search O(n), insert and delete O(1) at either end or at a node you already hold.
• Stack (push, pop, peek): O(1). Search O(n).
• Queue (enqueue, dequeue, peek): O(1). Search O(n).
• Hash table: search, insert and delete O(1) average, O(n) worst case. No index access.
• Binary search tree (unbalanced): search, insert, delete O(log n) average, O(n) worst case (a sorted insert order turns it into a list).
• Balanced BST (red-black, AVL): search, insert, delete O(log n) guaranteed.
• Binary heap: peek at min or max O(1), insert O(log n), remove min or max O(log n), search O(n), build from n items O(n).
• Trie: search, insert, delete O(L) for a key of length L, independent of how many keys are stored. Space is up to O(N · L) nodes for N keys.

Sorting algorithms time complexity

• Bubble sort: best O(n) (with an early exit when no swaps happen), average O(n²), worst O(n²), space O(1), stable.
• Selection sort: O(n²) in every case, space O(1), not stable.
• Insertion sort: best O(n) on sorted input, average and worst O(n²), space O(1), stable. Fast for small or nearly sorted arrays.
• Merge sort: O(n log n) in every case, space O(n), stable.
• Quicksort: best and average O(n log n), worst O(n²), space O(log n) for the recursion on average, not stable.
• Heap sort: O(n log n) in every case, space O(1), not stable.
• Counting sort: O(n + k) where k is the range of values, space O(n + k), stable.
• Radix sort: O(d · (n + b)) for d digits in base b, space O(n + b), stable.
• Timsort: best O(n) on already-sorted runs, average and worst O(n log n), space O(n), stable.

No sort that works only by comparing elements can beat O(n log n) in the worst case, which is why merge sort, heap sort and Timsort are considered optimal. Counting and radix sort escape that limit because they look at the values themselves, so they only work for keys like small integers or fixed-length strings.

Which sorting algorithm does Java use?

According to the Arrays Javadoc, Arrays.sort on primitive arrays (int[], long[], double[] and the rest) uses a Dual-Pivot Quicksort that "offers O(n log(n)) performance on all data sets". In the JDK 25 source it switches to heap sort if the partitioning recursion gets too deep, which is how it avoids quicksort's O(n²) worst case. Stability does not matter for primitives, because two equal ints are indistinguishable.

For objects, Arrays.sort(Object[]), Collections.sort and List.sort use a stable, adaptive merge sort based on Timsort. Stability matters here: if you sort employees by department after sorting them by name, employees within each department stay in name order.

Java collections time complexity

• ArrayList: get(i) and set(i) O(1); add(e) O(1) amortized; add(i, e) and remove(i) O(n) (they shift elements; removing the last element is O(1)); contains and indexOf O(n).
• LinkedList: addFirst, addLast, removeFirst, removeLast O(1); get(i) O(n), walking from whichever end is closer; contains O(n).
• ArrayDeque: offer, push, poll, pop and peek at either end O(1) amortized; contains and remove(Object) O(n).
• HashMap and HashSet: get, put, remove and containsKey O(1) average. Tree bins limit the worst case (see below). Iteration is O(capacity + size).
• LinkedHashMap: same costs as HashMap, plus predictable iteration order.
• TreeMap and TreeSet: get, put, remove, containsKey O(log n), guaranteed (a red-black tree); firstKey, floorKey, ceilingKey O(log n).
• PriorityQueue: peek O(1); offer and poll O(log n); remove(Object) and contains O(n).

Most of these figures are stated in the Java 25 Javadoc of each class; the PriorityQueue page, for example, spells out O(log n) for enqueue and dequeue, linear time for remove(Object) and contains, and constant time for peek.

What is the worst-case time complexity of HashMap?

Since Java 8, a HashMap bucket that collects too many entries is converted from a linked list into a balanced tree. The threshold constant is TREEIFY_THRESHOLD = 8, and it only happens once the table has at least MIN_TREEIFY_CAPACITY = 64 buckets; below that, the map resizes instead. The JDK source comments describe this as providing worst-case O(log n) operations when keys have distinct hashes or implement Comparable. If many keys share a hash code and are not comparable, a lookup can still degrade toward O(n). The practical lesson: write a good hashCode, and make key classes Comparable when collisions are likely. The HashMap internals guide walks through buckets, resizing and tree bins step by step.

Common Big-O mistakes in interviews

• Calling two different inputs n. Looping over a string of length n for each of m words is O(n · m), not O(n²).
• Forgetting the cost of sorting. "Sort, then two pointers" is O(n log n), not O(n).
• Ignoring library calls. contains on a list, remove(0) on an ArrayList and string += inside a loop each add a factor of n.
• Quoting hash tables as O(1) without the caveat. Say "O(1) on average"; mention the worst case if asked.
• Forgetting recursion stack space. A recursive DFS on a skewed tree uses O(n) stack.
• Counting output size wrong. Generating all subsets is at least O(2ⁿ) because that is how many subsets there are; no trick avoids it.
• Keeping constants and lower terms. O(2n + 10) is just O(n).

Once you can read complexity quickly, the next step is recognizing which technique gets you to the target complexity. The DSA patterns sheet maps problem signals to 15 patterns, each with its complexity and a Java template.

Practice with the full question bank

• Master Data Structures & Algorithms with Our Handwritten Notes: concise handwritten DSA notes with flowcharts and diagrams, built for product-company interview prep and quick revision.
• Complete Collections Framework Q&A: 100 Java Collections Framework interview questions with detailed answers, code examples and performance tips.

Related reading

• DSA patterns sheet in Java: 15 patterns that solve most coding interview problems
• How HashMap works internally in Java
• Common data structures and algorithms interview questions

FAQ

What is the time complexity of HashMap get and put in Java?

O(1) on average, assuming a reasonable hashCode. In the worst case a crowded bucket is turned into a tree, which bounds lookups at O(log n) when keys have distinct hashes or are Comparable; otherwise a lookup can degrade toward O(n).

Is O(log n) faster than O(n)?

For large inputs, yes, by a huge margin: for a million elements, log₂ n is about 20. For very small inputs, a simple O(n) loop can beat an O(log n) structure because of lower constant factors, which is why Big-O is about growth, not exact speed.

What is the difference between time complexity and space complexity?

Time complexity describes how the number of steps grows with the input size; space complexity describes how the extra memory grows. Both use Big-O notation, and improving one often costs the other, as with caching or memoization.

What is the time complexity of ArrayList contains and remove?

contains and indexOf are O(n) because they scan the list. remove(index) is O(n) because it shifts the following elements left; removing the last element is O(1). If you need fast membership checks, use a HashSet.

Why is O(n log n) the best possible for sorting?

Any sort that only compares pairs of elements must be able to produce every one of the n! possible orderings, and each comparison gives one yes/no answer, so it needs about log₂(n!) comparisons, which grows as n log n. Non-comparison sorts like counting and radix sort can be faster for suitable keys.

Do constants matter in Big-O?

Not in the notation: O(2n) and O(n) are the same class. They do matter in practice, so when two solutions have the same Big-O, mention the constant factors, memory use and cache friendliness as tie-breakers.