Common Complexities

March 2026 · 24 min read

This is the gallery of all complexity classes you'll encounter in practice. For each one: what it looks like in code, why it has that complexity (with derivation), and which real algorithms fall into it.

$O(1)$: Constant Time

The operation takes the same time regardless of input size.

int getFirst(vector<int>& arr) {
    return arr[0];  // one memory access, always
}

Derivation: No loops, no recursion. The number of operations is fixed (1 comparison, 1 return). $T(n) = c$ for some constant $c$. Since $c \leq c \cdot 1$ for all $n$, $T(n) = O(1)$.

Real examples: Array access by index, hash table lookup (average), stack push/pop, queue enqueue/dequeue.

$O(\log n)$: Logarithmic Time

The input is halved (or reduced by a constant fraction) at each step.

int binarySearch(vector<int>& arr, int target) {
    int lo = 0, hi = arr.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

Derivation: Each iteration cuts the search range in half. After $k$ iterations, the range has size $n / 2^k$. We stop when $n / 2^k \leq 1$, i.e., $k \geq \log_2 n$. So:

Real examples: Binary search, BST operations (balanced), exponentiation by squaring, finding in a sorted rotated array.

$O(\sqrt{n})$: Square Root Time

bool isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

Derivation: The loop runs while $i^2 \leq n$, i.e., $i \leq \sqrt{n}$. Iterations: $\sqrt{n} - 1 = O(\sqrt{n})$.

Real examples: Trial division, sqrt decomposition for range queries.

$O(n)$: Linear Time

We look at each element exactly once (or a constant number of times).

int findMax(vector<int>& arr) {
    int mx = arr[0];
    for (int i = 1; i < arr.size(); i++) {
        if (arr[i] > mx) mx = arr[i];
    }
    return mx;
}

Derivation: One loop, $n - 1$ iterations, $O(1)$ work per iteration. $T(n) = n - 1 = O(n)$.

Real examples: Linear search, counting sort (with limited range), finding min/max, computing prefix sums, Kadane's algorithm.

$O(n \log n)$: Linearithmic Time

This is the sweet spot for efficient divide-and-conquer algorithms.

void mergeSort(vector<int>& arr, int l, int r) {
    if (l >= r) return;
    int mid = (l + r) / 2;
    mergeSort(arr, l, mid);
    mergeSort(arr, mid + 1, r);
    merge(arr, l, mid, r);  // O(n) merge
}

Derivation: The recurrence is $T(n) = 2T(n/2) + O(n)$. By the Master Theorem (Case 2, $a = 2, b = 2, f(n) = n, \log_b a = 1$):

Alternatively, by recursion tree: there are $\log n$ levels, each doing $O(n)$ total work. Total: $n \times \log n$.

Real examples: Merge sort, heap sort, FFT, closest pair of points.

$O(n^2)$: Quadratic Time

void bubbleSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j+1])
                swap(arr[j], arr[j+1]);
        }
    }
}

Derivation:

Real examples: Bubble sort, insertion sort (worst case), selection sort, all-pairs computations, naive string matching.

$O(n^3)$: Cubic Time

// Standard matrix multiplication: C = A × B
void matMul(int A[][N], int B[][N], int C[][N], int n) {
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            C[i][j] = 0;
            for (int k = 0; k < n; k++)
                C[i][j] += A[i][k] * B[k][j];
        }
}

Derivation: Three nested loops, each running $n$ times. $T(n) = n \times n \times n = n^3 = O(n^3)$.

Real examples: Naive matrix multiplication, Floyd-Warshall shortest paths, some dynamic programming on intervals.

$O(2^n)$: Exponential Time

int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);  // two recursive calls
}

Derivation: The recurrence is $T(n) = T(n-1) + T(n-2) + O(1)$. Since $T(n) \geq 2T(n-2)$ (each call spawns two), by induction:

More precisely, $T(n) = \Theta(\phi^n)$ where $\phi = \frac{1+\sqrt{5}}{2} \approx 1.618$ (the golden ratio). This is $O(2^n)$ but also $\Omega(1.618^n)$.

Real examples: Naive Fibonacci, subset enumeration, brute-force satisfiability, recursive power set.

$O(n!)$: Factorial Time

void permute(vector<int>& arr, int l, int r) {
    if (l == r) {
        process(arr);  // O(n) or O(1)
        return;
    }
    for (int i = l; i <= r; i++) {
        swap(arr[l], arr[i]);
        permute(arr, l + 1, r);
        swap(arr[l], arr[i]);
    }
}

Derivation: At level 0, we make $n$ choices. At level 1, $n-1$ choices. And so on. Total leaf calls:

Real examples: Generating all permutations, brute-force TSP, brute-force Hamiltonian path.

Growth Rate Comparison

The ", " entries exceed the number of atoms in the observable universe ($\approx 10^{80}$).

Maximum Solvable Input Size

Assuming $10^8$ operations per second and a 1-second time limit:

This table is extremely useful in competitive programming for choosing the right algorithm based on the input constraints.

Summary

• $O(1)$: Direct access, hash table. No loops.
• $O(\log n)$: Halving at each step. Binary search, balanced BST.
• $O(n)$: Single pass. Scanning, counting.
• $O(n \log n)$: Divide-and-conquer with linear merge. Optimal sorting.
• $O(n^2)$: Nested loops over all pairs. Simple sorting algorithms.
• $O(2^n)$: All subsets. Exponential blowup from branching recursion.
• $O(n!)$: All permutations. The most expensive common class.