Big O notation

Big O notation describes how a piece of code scales. Not how fast it runs on your laptop right now, but how its runtime or memory usage grows as the input gets larger. LeetCode problems list constraints like 1 <= n <= 10^5 precisely so you can rule out slow solutions before you write them.

The input size is almost always called n. From there, the common complexity classes you’ll see in practice are these:

---

O(1): constant

The operation takes the same time regardless of input size. A dictionary lookup is O(1). Whether the dictionary holds 10 items or 10 million, seen[num] is one step.

seen = {}
seen[2] = 0       # O(1) write
print(seen[2])    # O(1) read

O(log n): logarithmic

The algorithm halves its search space at each step. Binary search is the clearest example: start at the middle of a sorted array, decide which half holds the target, repeat. With 1,000 elements you need about 10 steps. With 1,000,000 elements, about 20. The input grows by 1,000x and the work grows by 2x.

O(n): linear

One pass through the input. Finding the maximum value in an unsorted list is O(n). Building the hash map in Two Sum is O(n): you look at each element exactly once.

for i, num in enumerate(nums):   # O(n): touches each element once
    complement = target - num
    if complement in seen:
        return [seen[complement], i]
    seen[num] = i

O(n log n): linearithmic

This is where efficient sorting lands. Python’s built-in sorted() and list.sort() use Timsort, which runs in O(n log n). It is much faster than O(n²) for large inputs, and in the general case you cannot sort by comparing elements any faster than this.

O(n²): quadratic

Two nested loops over the same input. The brute-force Two Sum, where you try every pair of indices, runs in O(n²). For n = 10,000 that’s 100 million operations. Problems with n <= 10^5 will time out with a quadratic solution.

for i in range(len(nums)):
    for j in range(i + 1, len(nums)):   # O(n²): nested loops
        if nums[i] + nums[j] == target:
            return [i, j]

O(2^n): exponential

Appears in recursion that branches at every step, like generating all subsets of a set. Impractical for n larger than 20 or 30.

---

How to read complexity off code

You rarely need to prove a complexity formally. For most problems you can read it straight off the shape of the code with a few rules. The question to keep asking is: how many times does this touch the input as n grows?

A single loop over the input is O(n). The body runs once per element.

for x in nums:      # runs n times
    total += x      # constant work each time
# O(n)

Nested loops over the input multiply. A loop inside a loop, each running over n elements, does n times n steps.

for i in nums:          # n times
    for j in nums:      # n times for each i
        check(i, j)     # constant work
# O(n * n) = O(n²)

Loops one after another add, and the larger one wins. An O(n) pass followed by another O(n) pass is O(2n), which is just O(n). An O(n) pass followed by an O(n²) pass is O(n²).

for x in nums:      # O(n)
    ...
for x in nums:      # O(n)
    ...
# O(n) + O(n) = O(n)

Halving the work each step is O(log n). If a loop cuts its range in two every iteration, like binary search, it finishes in about 10 steps for a thousand items and 20 for a million.

Work that does not depend on n is O(1). Indexing a list, reading a dict key, or doing arithmetic is one step no matter how large the input is.

For recursion, add up the work across all the calls it makes. Flattening a nested list makes one call per sublist and handles each element once overall, so it is O(n) in total. A function that splits into two fresh calls at every level makes about 2^n calls, each doing a little work, which is O(2^n).

---

A few things to keep in mind

Big O is worst case by default. O(n) means the algorithm won’t do more than n operations for an input of size n. It says nothing about the average case; if that matters, it’s stated separately.

Constants are dropped. An algorithm that does exactly 3n operations is still called O(n), because constants become irrelevant as n grows. Similarly, O(n + n²) simplifies to O(n²): the dominant term wins.

---

Space complexity

Space complexity measures the extra memory an algorithm needs as the input grows, written with the same notation as time. It answers “how much more memory when n gets bigger”, not “how many bytes exactly”.

O(1) space is a fixed number of variables, whatever the input size.

def total(nums):
    s = 0                # one variable, does not grow
    for x in nums:
        s += x
    return s
# O(1) extra space

O(n) space is a structure that grows with the input, like a copy, a set, or a dict of its elements.

def has_repeat(nums):
    seen = set()         # grows to hold up to n items
    for x in nums:
        if x in seen:
            return True
        seen.add(x)
    return False
# O(n) extra space

Two kinds of space are worth separating. The result you return is output space. The scratch memory used while computing is auxiliary space. When a problem asks for O(1) space it means auxiliary: returning a list of n answers is unavoidably O(n) of output, and that does not count against you.

Recursion costs space even when it stores nothing. Each call still in progress keeps a frame on the call stack holding its own variables, and the frames pile up until they return. The most frames open at once is the depth of the recursion, so a recursive function is O(d) space, where d is that depth, on top of anything it allocates. A function that recurses n levels deep uses O(n) stack space by itself.

The hash map in Two Sum costs O(n) time and O(n) space: one pass, but you pay in memory. The brute-force version costs O(n²) time and O(1) space: slow, but uses almost no extra memory. That tradeoff, faster runtime for more memory, shows up constantly in LeetCode problems.

---

Quick reference

Complexity	Name	Typical example
O(1)	Constant	dict lookup, array index
O(log n)	Logarithmic	binary search
O(n)	Linear	single loop, Two Sum with hash map
O(n log n)	Linearithmic	Timsort (Python’s sorted()), merge sort
O(n²)	Quadratic	nested loops, Two Sum brute force
O(2^n)	Exponential	all subsets, naive recursion