Time Complexity

Why not just time the code?

You could run two solutions and compare stopwatches, but the result would depend on your laptop, the language, and what else was running. Complexity analysis instead measures how the work grows as the input grows. That answer is the same everywhere.

We care about growth because inputs get bigger. A solution that takes 1 second on 1,000 items might take 1 second on 10,000 items, or it might take 100 seconds. Time complexity tells you which.

The common growth classes

What the difference actually means

For $n = 1{,}000{,}000$, assuming a rough one million operations per second:

This is why $O(n^2)$ solutions fail on large inputs in coding rounds. It is not that they are wrong — they simply never finish.

Quick check

Before moving on, order these from fastest-growing to slowest: $O(n^2)$, $O(\log n)$, $O(n)$, $O(2^n)$.

$O(2^n) > O(n^2) > O(n) > O(\log n)$ — exponential dwarfs quadratic, which dwarfs linear, which dwarfs logarithmic.

The full family of notations

Big O is the one everyone quotes, but it is only one member of a family called asymptotic notation. Each member answers a slightly different question about how a function grows.

Big O — the upper bound

$f(n) = O(g(n))$ means $f$ grows no faster than $g$, for large enough $n$. It is a ceiling — the algorithm is at most this bad.

Formally: there exist constants $c > 0$ and $n_0$ such that $f(n) \le c \cdot g(n)$ for all $n \ge n_0$.

f(n) = 3n + 5   →   O(n)

Because $3n + 5$ never grows faster than, say, $4n$ once $n$ is large enough.

This is what interviews mean by default when they say "what is the complexity" — the worst-case upper bound.

Big Omega (Ω) — the lower bound

$f(n) = \Omega(g(n))$ means $f$ grows at least as fast as $g$. It is a floor — the algorithm takes at least this long.

Linear search is Ω(1)   — best case, found immediately
Linear search is O(n)   — worst case, scanned everything

Omega and O are opposites. O caps the worst case; Ω floors the best case.

Big Theta (Θ) — the tight bound

$f(n) = \Theta(g(n))$ means $f$ grows exactly as fast as $g$ — both an upper and lower bound at once. This is the most precise statement you can make.

Summing an array is always exactly n additions.
That is Θ(n) — not just "at most n", but "exactly proportional to n" every time.

If best case and worst case are the same order, you can say Θ. If they differ — like linear search's best case $O(1)$ versus worst case $O(n)$ — you cannot; you can only bound each case separately with O or Ω.

Little o — the strict upper bound

$f(n) = o(g(n))$ means $f$ grows strictly slower than $g$ — it says "and never catches up", not just "does not exceed".

n = o(n^2)     true, n is strictly smaller for large n
n = O(n)       true
n = o(n)       false — n does not grow strictly slower than itself

The difference from Big O: $O$ allows $f$ and $g$ to grow at the same rate (up to a constant). Little $o$ demands $f$ becomes insignificant compared to $g$ as $n$ grows.

Little omega (ω) — the strict lower bound

$f(n) = \omega(g(n))$ is the mirror of little o: $f$ grows strictly faster than $g$.

n^2 = ω(n)     true, n² eventually dwarfs n
n = ω(n)       false — equal growth, not strictly faster

The full picture, side by side

You will use $O$ in nearly every interview answer. $\Theta$ comes up when someone asks "is that bound tight?". $\Omega$, little $o$ and little $\omega$ mostly appear in academic contexts or when a professor is testing whether you understand what Big O actually promises.

Quick check

Which notation would you use to say "this algorithm takes exactly n² steps, no more, no less, on every input"?

$\Theta(n^2)$ — since both the upper and lower bound are the same, the tight bound applies.

Why we drop constants and lower-order terms

If an algorithm does $3n + 50$ operations, we call it $O(n)$ — not $O(3n + 50)$.

We drop the constants because they do not affect the shape of the curve. For large $n$, the difference between $3n$ and $n$ is a fixed multiple, while the difference between $n$ and $n^2$ grows without limit. Big O cares about the shape, not the exact count.

f(n) = 3n + 50        →  O(n)
f(n) = 5n² + 3n + 100 →  O(n²)     the n² term dominates everything else

Working out the complexity

Rule 1: Count the loops over the input

A single pass is linear.

def total(nums):
    result = 0
    for n in nums:      # runs n times
        result += n
    return result

This is $O(n)$.

Practice question

What is the time complexity of this function?

def print_pairs_sum(nums, k):
    for n in nums:
        if n == k:
            print(n)

Rule 2: Nested loops multiply

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

The inner loop runs for each iteration of the outer, so this is $O(n^2)$.

Practice question

What is the complexity of three nested loops, each running $n$ times?

$O(n^3)$ — each additional nested loop multiplies in another factor of $n$.

Rule 3: Sequential blocks add, then you keep the largest

def process(nums):
    for n in nums:      # O(n)
        print(n)

    for a in nums:          # O(n^2)
        for b in nums:
            print(a, b)

That is $O(n) + O(n^2) = O(n^2)$. The smaller term disappears because it stops mattering as $n$ grows.

Practice question

A function does an $O(n \log n)$ sort, then a single $O(n)$ pass over the result. What is the overall complexity?

$O(n \log n)$ — it dominates $O(n)$, since $n \log n$ grows faster than $n$ alone.

Rule 4: Halving the input each step is logarithmic

def binary_search(nums, target):
    low, high = 0, len(nums) - 1

    while low <= high:
        mid = (low + high) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1

Each iteration throws away half the remaining range, so the loop runs about $\log_2 n$ times. For a million items, that is roughly 20 steps.

Note the C++ version uses low + (high - low) / 2 rather than (low + high) / 2. With large indices the naive form can overflow a 32-bit int and produce a negative midpoint. Python integers are arbitrary precision, so it never bites there — but the habit is worth carrying across.

Practice question

An algorithm halves its input at every step, doing $O(1)$ work per step. What is its time complexity?

$O(\log n)$ — the number of halvings needed to shrink $n$ down to 1 is $\log_2 n$.

Best, average and worst case

Every one of the notations above (O, Ω, Θ) can be applied to three different scenarios:

• Best case — the friendliest possible input
• Average case — a typical, random input
• Worst case — the least friendly possible input

Take linear search for a target that may or may not be present:

• Best case — the target is first. $O(1)$, or more precisely $\Theta(1)$.
• Average case — the target is somewhere in the middle. $\Theta(n)$.
• Worst case — the target is last or absent. $\Theta(n)$.

Unless stated otherwise, assume worst case. It is the only bound that guarantees anything — a best-case claim tells you nothing about what happens on a bad day, and interviewers are testing whether your solution survives one.

Practice question

Quicksort has an average time complexity of $O(n \log n)$ but a worst case of $O(n^2)$. If someone asks "what is the time complexity of quicksort?" with no further context, which should you give?

State both, but lead with the worst case: "$O(n^2)$ worst case, $O(n \log n)$ average — the worst case happens with a poor pivot choice, like an already-sorted array with a naive last-element pivot." That answer signals real understanding rather than a memorised number.

Test yourself

Work out the complexity of this function before reading on, then run it to check your reasoning.

The first loop is $O(n)$ and the nested loop is $O(n^2)$. Added together and keeping the dominant term, the function is $O(n^2)$.

One more round of practice

Try to state the tightest notation you can (Big O is fine, Θ is better if you can justify it) before checking each answer.

$\Theta(n)$ — every input of size $n$ takes exactly the same number of steps, so the bound is tight in both directions.

2. A function checks if the first element of an array equals a target, and returns immediately either way.

$\Theta(1)$ — constant work regardless of array size.

$O(2^n)$ — each call branches into two more calls, and the tree of calls roughly doubles in size at each level.

4. A hash map lookup, in the worst case where every key collides into one bucket.

$O(n)$ worst case, even though it is $O(1)$ on average. Interviewers who ask "what if every key collides?" are testing whether you know the worst case exists at all.

5. Generating every permutation of an array of size $n$.

$O(n!)$ — there are $n!$ distinct orderings, and producing each one takes at least constant work.

Common mistakes

1. Keeping constants. $O(2n)$ is just $O(n)$. Write the simplified form.
2. Forgetting hidden costs. Sorting inside a loop is not free — sort() is $O(n \log n)$ every time it runs.
3. Assuming nested loops are always quadratic. If the inner loop runs a fixed number of times, it is still $O(n)$.
4. Confusing $O(\log n)$ with $O(n \log n)$. The first halves the problem; the second does linear work at each of $\log n$ levels.
5. Using Big O when Big Theta is meant. Saying "the complexity is $O(n)$" for an algorithm that always takes exactly $n$ steps is technically true but weaker than saying $\Theta(n)$ — O only claims a ceiling, Θ claims the exact shape.
6. Quoting only the average case. Always mention the worst case unless the question specifically asks for average.

Summary

Time complexity describes growth, not wall-clock time. Big O gives an upper bound, Big Omega a lower bound, and Big Theta a tight bound that pins down both at once — little o and little omega are their strict versions, mostly seen in academic settings. Count loops, multiply when nested, add when sequential and keep the dominant term, and always default to worst case unless told otherwise.