Big-O Complexity

Big-O is a way of describing how the amount of work an algorithm does grows as its input grows. It throws away all the details that don't matter at scale, the exact hardware, the constant setup costs, the small terms, and keeps only the part that dominates when the input gets large. When an interviewer asks "what's the complexity?" they are really asking: if I ten-times the data, does your runtime barely move, ten-times, or explode?

The reason it matters is that constants lie and growth rates don't. An algorithm that does 100n operations beats one that does n² the moment n passes 100, and from there the gap only widens. On a million-element array, an $O(n)$ method finishes in a blink while an $O(n^2)$ method does a trillion steps and effectively never returns. Getting the growth rate right is usually the difference between a solution that passes and one that times out.

We write

$$T(n) = O\big(f(n)\big)$$

to mean: beyond some input size, the running time $T(n)$ is at most a constant multiple of $f(n)$. Here $n$ is the size of the input (array length, number of nodes), $f(n)$ is the growth shape we care about ($n$, $n^2$, $\log n$, …), and the hidden constant is exactly what Big-O lets us ignore. So $O(n)$ and $O(100n)$ are the same class: both grow linearly.

The classes worth knowing cold

Big-O	Name	Where it shows up
$O(1)$	constant	hash lookup, array index, stack push
$O(\log n)$	logarithmic	binary search, balanced-tree / heap operations
$O(n)$	linear	one pass over an array, two-pointer scans
$O(n \log n)$	linearithmic	good sorting, heap-based top-k
$O(n^2)$	quadratic	nested loops over the same array
$O(2^n)$	exponential	brute-forcing every subset

Worked example: does this list have a duplicate?

Two ways to check whether an array of n numbers contains any repeat.

The nested-loop way compares every element to every other one:

def has_dup_slow(a):          # O(n^2) time, O(1) space
    for i in range(len(a)):
        for j in range(i + 1, len(a)):
            if a[i] == a[j]:
                return True
    return False

The outer loop runs n times, the inner up to n times, so the work is proportional to $n^2$. The hash-set way remembers what it has seen:

def has_dup_fast(a):          # O(n) time, O(n) space
    seen = set()
    for x in a:
        if x in seen:
            return True
        seen.add(x)
    return False

One pass, and each in/add on a set is $O(1)$ on average, so the whole thing is $O(n)$. Put numbers on it: at $n = 10{,}000$, the slow version does about 50 million comparisons; the fast one does 10,000 lookups. That is a 5,000-times difference, and it grows with n. The trade is memory: the fast version stores up to n items, so it is $O(n)$ space. Reporting both time and space is what interviewers want.

Reading complexity off code

Two quick rules cover most interview code. Sequential blocks add ($O(n) + O(n) = O(n)$); nested loops multiply (a loop of n inside a loop of n is $O(n^2)$). Halving the search space each step, as binary search does, gives $O(\log n)$, because you can only halve n about $\log_2 n$ times before nothing is left.

Where it misleads

• Constants matter at small n. $O(n^2)$ can beat $O(n \log n)$ on tiny inputs, which is why real sort routines switch to insertion sort under a threshold. Big-O is an asymptotic claim.
• Worst case is not average case. A hash lookup is $O(1)$ on average but $O(n)$ if every key collides; quicksort is $O(n \log n)$ typically but $O(n^2)$ on an adversarial input. Say which case you mean.
• Space counts too. A blazing $O(n)$-time method that allocates an $O(n)$ hash map may lose to an in-place $O(n \log n)$ one under a tight memory limit.

In quant-dev interviews, complexity is the very first thing you say after describing an approach and the last thing you check before coding: "this is $O(n \log n)$ time, $O(n)$ space, can we do better?" Being fluent in it lets you compare the Arrays and Two Pointers, Hash Maps and Sets, and Binary Search Patterns tricks and pick the one that fits the size of the data.