Big-O Notation

Big-O describes how an algorithm's running time or space grows with input size, ignoring constants and lower-order terms.

1. The idea

Big-O notation classifies algorithms by their worst-case growth rate as input size $n$ grows large, letting you compare approaches without worrying about hardware-specific constants. $f (n) = O (g (n))$ means $f$ grows no faster than a constant multiple of $g$ for large $n$ .

Common classes, from fastest to slowest growth: $O (1)$ constant, $O (lo g n)$ logarithmic, $O (n)$ linear, $O (n lo g n)$ linearithmic, $O (n^{2})$ quadratic, $O (2^{n})$ exponential. Interviewers expect you to identify which class an algorithm falls into and justify it by counting operations.

Space complexity follows the same notation but measures auxiliary memory used, which matters separately from time — an algorithm can be fast but memory-hungry, or slow but memory-light.

2. Why it matters

Every quant-dev interview expects you to state and justify the time and space complexity of any algorithm you propose, often before writing code.

3. Core mathematics

Definition

f (n) = O (g (n)) ⟺ \exists c > 0, n_{0} s.t. f (n) \leq c g (n) \forall n \geq n_{0}

Nested loop over n items

O (n^{2})

Two nested loops each over n elements

Divide and conquer recurrence (e.g. merge sort)

T (n) = 2 T (n /2) + O (n) ⟹ T (n) = O (n lo g n)

4. How to recognize it

Think of this when…

Asks to analyze the time or space complexity of a described algorithm
Compares two approaches to the same problem by efficiency
Involves nested loops, recursion, or halving the input

5. Worked example

Worked example

You have an array of n unsorted integers and want to find if any two sum to a target value. Compare the brute-force approach to a hash-set approach.

1
Brute force checks every pair of indices with nested loops.
$O (n^{2}) time, O (1) extra space$
2
Hash-set approach: for each element, check if (target - element) has been seen, then add the element.
$O (n) time, O (n) extra space$
Answer: The hash-set approach trades $O (n)$ extra space for reducing time from $O (n^{2})$ to $O (n)$ — a classic time/space tradeoff.

6. Common mistakes

Confusing average-case with worst-case complexity
Ignoring space complexity when only asked about speed
Dropping necessary terms — e.g. saying an algorithm with a preprocessing sort plus a linear scan is $O (n)$ instead of $O (n lo g n)$

7. Quick check

A single loop over n elements followed by a separate single loop over n elements is:

Binary search has time complexity:

8. Practice

3 QuantSolve questions use this concept.

Practice this concept

9. Related methods

This lesson is conceptual; see the topic hub for methods.

Create a free account to save lesson progress.