Big-O Notation: Time and Space Complexity Explained

Big-O notation is the language engineers use to describe how an algorithm’s cost grows as its input gets larger. It is the single most important piece of vocabulary in DSA — without it, you cannot compare two solutions or explain why one is better than another. This post covers what Big-O measures, how to read it off code, and the classes you’ll see again and again.

What Big-O actually measures

Big-O describes how the runtime (or memory usage) of an algorithm grows as a function of the input size n. It is deliberately a rough measure — it ignores constant factors and lower-order terms.

If an algorithm takes 3n + 7 operations on an input of size n, we say it is O(n). The 3 and the 7 don’t matter for large n; what matters is that doubling the input roughly doubles the time.

The mental model: pretend n gets enormous. Which term dominates?

• 100n + 5 → O(n)
• n^2 + 1000n → O(n²) (the n² term wins for large n)
• 5 → O(1) (a constant, regardless of input)

This is why Big-O ignores constants: on a fast computer 100n is slow, on a faster computer it’s fast, but the shape of the curve is the same.

The common complexity classes

You will see these constantly. Memorise the order from cheapest to most expensive:

O(1)  <  O(log n)  <  O(n)  <  O(n log n)  <  O(n^2)  <  O(2^n)  <  O(n!)

Let’s walk through each with code.

O(1) — constant time

The work doesn’t depend on input size.

def get_first(nums):
    return nums[0]    # one indexing operation

Indexing a list, looking up a key in a dictionary, returning a fixed value — all O(1).

O(log n) — logarithmic time

Each step cuts the problem in half. The classic example is binary search.

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

print(binary_search([1, 3, 5, 7, 9, 11], 7))    # 3

For a list of a million elements, binary search takes about 20 comparisons. That is the magic of logarithmic time.

O(n) — linear time

You touch every element once.

def total(nums):
    s = 0
    for x in nums:
        s += x
    return s

print(total([1, 2, 3, 4]))    # 10

Most “scan once” patterns are O(n) — finding a max, counting matches, building a transformed list.

O(n log n) — linearithmic time

The cost of efficient sorting algorithms (merge sort, heap sort, Python’s built-in sorted).

nums = [5, 2, 9, 1, 7]
print(sorted(nums))    # O(n log n)

A useful intuition: O(n log n) is roughly “do O(log n) work n times” or “do O(n) work log n times.” Either framing fits sorting.

O(n²) — quadratic time

A nested loop where both layers go over the input.

def has_duplicate(nums):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] == nums[j]:
                return True
    return False

Quadratic algorithms are fine for small n but painful at scale. 10,000 elements is 100 million comparisons.

O(2ⁿ) — exponential time

Each input element doubles the work. Naive recursive Fibonacci is the textbook case.

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(10))    # 55
# fib(40) already takes seconds; fib(50) takes minutes.

Exponential algorithms are essentially unusable past n ≈ 30 unless you optimise them (usually with memoization, turning O(2ⁿ) into O(n)).

O(n!) — factorial time

Generating every permutation of an input.

from itertools import permutations
print(list(permutations([1, 2, 3])))
# 3! = 6 permutations

10! is about 3.6 million. 15! is over a trillion. Anything factorial is only viable for tiny inputs.

Visualising the difference

For n = 1,000,000 and one operation per nanosecond:

This table is why senior engineers obsess about complexity. The gap between O(n) and O(n²) is the gap between “instant” and “your service is down.”

How to read code and assign a Big-O

Three rules cover most cases.

Rule 1 — sequential code adds. Two O(n) loops in a row are still O(n), because O(n) + O(n) = O(2n) = O(n). Constants don’t matter.

Rule 2 — nested loops multiply. A loop of size n containing a loop of size m is O(n × m). If both are n, that’s O(n²).

Rule 3 — recursive calls follow the recursion tree. The total work is the number of nodes in the tree times the work per node. Binary search has a tree of depth log n and O(1) per node → O(log n).

def example(nums):
    # O(n)
    for x in nums:
        print(x)

    # O(n^2)
    for x in nums:
        for y in nums:
            print(x, y)

    # Total: O(n) + O(n^2) = O(n^2)

When in doubt, count the dominant loop or call.

# A
def a(nums):
    return nums[len(nums) // 2]

# B
def b(nums):
    s = 0
    for x in nums:
        for y in nums:
            s += x * y
    return s

# C
def c(n):
    if n <= 1:
        return 1
    return c(n // 2) + 1

Best, average, and worst case

Big-O most often describes the worst case — the upper bound on runtime regardless of input. That’s the safe number to report.

def linear_search(arr, target):
    for i, x in enumerate(arr):
        if x == target:
            return i
    return -1

• Best case — target is at index 0 → O(1)
• Average case — target is somewhere in the middle → O(n/2) = O(n)
• Worst case — target is at the end or missing → O(n)

In interviews and in design discussions, “the complexity is O(…)” almost always means worst case. If you need to call out a different case, do so explicitly: “average case O(n), worst case O(n²)” — that’s the way quicksort is usually described.

Amortized complexity in one minute

Some operations are usually cheap but occasionally expensive. Amortized complexity is the average cost per operation over a long sequence.

Python’s list.append is the textbook example. Most appends are O(1) — there’s room in the underlying buffer. Occasionally the list runs out of space and Python allocates a bigger buffer and copies everything over — that one append is O(n). But it happens rarely enough that the average cost per append, across many calls, is still O(1).

We say list.append is amortized O(1). In practice, treat it as O(1) and move on.

Space complexity

Space complexity asks: how much memory does the algorithm use as a function of n?

# O(1) space — just two counters
def total(nums):
    s = 0
    for x in nums:
        s += x
    return s

# O(n) space — building a new list of size n
def doubled(nums):
    return [x * 2 for x in nums]

# O(n) space — recursion depth equals n
def sum_recursive(nums, i=0):
    if i == len(nums):
        return 0
    return nums[i] + sum_recursive(nums, i + 1)

Recursive calls cost stack space — each pending call holds its local variables until the recursion unwinds. Deep recursion on a million-element list will blow the stack in most languages.

When a problem says “in-place,” it wants O(1) extra space — modify the input directly rather than building a new collection.

A worked example — three solutions, three complexities

Problem. Given a sorted list of integers, return True if any two of them sum to a target value.

Approach 1 — brute force. Try every pair.

def has_pair_sum_v1(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return True
    return False

Time: O(n²). Space: O(1).

Approach 2 — hash set. Walk once and check the complement.

def has_pair_sum_v2(nums, target):
    seen = set()
    for x in nums:
        if target - x in seen:
            return True
        seen.add(x)
    return False

Time: O(n). Space: O(n).

Approach 3 — two pointers. Since the list is sorted, walk inwards from both ends.

def has_pair_sum_v3(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        s = nums[lo] + nums[hi]
        if s == target:
            return True
        elif s < target:
            lo += 1
        else:
            hi -= 1
    return False

Time: O(n). Space: O(1).

Approach 3 is the best of both worlds, but only because the input is sorted. Big-O analysis is what reveals which solution is “best” — and what “best” means.

Common beginner mistakes

A few that trip everyone up at first:

1. Counting print/log statements. They don’t matter for Big-O. Focus on the loops and recursion.
2. Forgetting hash lookups are O(1) on average. This is what makes hash maps so powerful. They are O(n) worst case (when hashes collide), but in practice we treat them as O(1).
3. Calling in on a list and assuming it’s fast. x in some_list is O(n). x in some_set is O(1).
4. Treating list.insert(0, x) like append. Inserting at the front shifts everything — O(n).
5. Hidden loops inside built-ins. sorted(nums) is O(n log n), not O(1). "".join(strings) is O(total length).

When you read code, ask of every line: “what does this really cost?”

Practice problems

Try to assign a Big-O to each. Some are tricky — write down your reasoning.

1. Looking up a key in a dictionary of size n.
2. Reversing a list using slicing (nums[::-1]).
3. Checking membership with x in sorted_list using a plain loop.
4. Checking membership with x in sorted_list using binary search.
5. Finding the maximum of n numbers.
6. Sorting n numbers with Python’s sorted.
7. Computing all subsets of a set of n elements.
8. Counting the number of digits in a positive integer n.

(Answers: 1. O(1) avg, 2. O(n), 3. O(n), 4. O(log n), 5. O(n), 6. O(n log n), 7. O(2ⁿ), 8. O(log n).)

Recap

You now know:

• Big-O describes how cost grows with input size, ignoring constants and lower terms
• The common classes are O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ), O(n!)
• Sequential code adds; nested loops multiply; recursion follows the call tree
• Worst case is the default; best, average, and amortized exist for specific reasons
• Space complexity matters too — recursion depth and auxiliary collections both count
• A faster algorithm often beats a faster computer

Next steps

With Big-O in your pocket, you can read DSA problems with the right lens. Next we dive into the most foundational data structure of all — arrays.

→ Next: Arrays in DSA: Introduction

Questions or feedback? Email codeloomdevv@gmail.com.