Big O Cheat Sheet for Coding Interviews

Common complexities, ranked

The last column is what the class means at a modest input of 1,000 items. The gap between the rows is why a better class beats a faster machine.

What the input size tells you

Read this table backward before you pick an approach. It assumes about 100 million simple steps in about a second, which is a rule of thumb and not a law, but it tells you which classes are worth trying. If n can reach 100,000, an O(n²) answer is about 10 billion steps, and saying so before you write anything is a strong signal.

Reading the cost from your own code

You rarely need to recall a figure. Most answers come from a few rules applied to what you just wrote.

def has_close_pair(nums, gap):
    """True if two values differ by at most gap."""
    ordered = sorted(nums)                 # O(n log n) time, O(n) for the copy
    for i in range(len(ordered) - 1):      # n - 1 steps
        if ordered[i + 1] - ordered[i] <= gap:   # O(1) each
            return True
    return False                           # total: O(n log n) time, O(n) space


def longest_run_of_ones(bits):
    """Two loops, but j never revisits an index, so the total is O(n)."""
    best = i = 0
    while i < len(bits):
        j = i
        while j < len(bits) and bits[j] == 1:
            j += 1
        best = max(best, j - i)
        i = max(j, i + 1)                  # i jumps past what j has walked
    return best

The first function is the sum rule: the sort dominates the pass. The second is the trap in the other direction. It has a loop inside a loop and is still linear, because every index is walked once. Saying why is worth more than the answer itself, and it is the question interviewers ask next.

Data structure operations

These are the costs of the structures themselves. A language's built-in can differ or attach conditions, so for those use the language pages below. In the table, h is the height of a tree and m is the length of a key.

A graph has its own operations, and the choice of representation changes all of them. V is the number of nodes and E the number of edges.

Most interview graphs have far fewer edges than V², so an adjacency list is the default. Reach for a matrix when the graph is dense or the question keeps asking whether one specific edge exists. The graph patterns guide covers what to do once it is built.

Sorting algorithms

You will rarely write one of these in an interview, but you will often be asked what your language's sort costs, or why a counting sort beats O(n log n) here. A stable sort keeps equal items in their original order, which matters when you sort by one key and then another.

No sort based only on comparing pairs can beat O(n log n) in the worst case. Counting and radix sort get around that by reading the values themselves, which is why they need a limited range of keys. When an interviewer asks whether you can do better than O(n log n), this is usually the answer they are checking for.

How to state complexity out loud

A figure with no reasoning sounds like a guess, even when it is right. A strong answer has four parts, and takes about fifteen seconds:

1. Give both costs, time and then space, without waiting to be asked.
2. Derive them from your code, naming the part that dominates.
3. Name your variables, especially when there are two inputs.
4. Qualify the figure: average case, amortized, or not counting the output.

This sheet is the lookup table. For what interviewers actually ask and how to handle the follow-ups, read time and space complexity in interviews. To hear how yours sounds, a coding mock interview with Josh, Devana's AI interviewer, asks about your solution as you write it, and the report scores logic explanation and code defense from what you say.

What your language's built-ins cost

Each of these pages takes its figures from that language's own documentation, cites it, and leaves out what the documentation does not state.

• Python: list, dict, set, deque, heapq and str. Python publishes a full table, so this is the most complete of the four.
• JavaScript: Map, Set, Array, Object and strings. The specification promises very little, and that page says exactly what, and how to reason without it.
• Java: ArrayList, LinkedList, HashMap, TreeMap, HashSet, PriorityQueue and ArrayDeque, with the conditions the Javadoc attaches.
• C++: vector, unordered_map, map, set, priority_queue and deque, with average and worst cases.

Common mistakes

• Calling a hash lookup O(1) with no qualifier. It is O(1) on average, and an interviewer may ask about the worst case.
• Writing O(n²) for two loops over different inputs. It is O(m · n), and the difference can decide whether the approach is fast enough.
• Forgetting the call stack. A recursive solution with no other memory still uses space proportional to its depth.
• Treating a slice or a string concatenation as free. In Python, slicing a list is O(j - i), so a slice inside a loop can quietly make a solution quadratic.
• Claiming a nested loop is O(n²) on sight. If the inner index never goes back, the total can be O(n), so count the steps instead of the loops.