Time Complexity Analysis

Throughout this course you'll see claims like "push_back is amortized O(1)" or "hash table lookups are O(1) on average" or "this graph algorithm runs in O(E log E)." This primer defines what that notation means and shows you how to derive it yourself. Treat it as a reference: read it once before the data-structures block (Lectures 7 onward), then come back whenever a lecture cites a complexity you want to understand.

Why We Analyze Time Complexity

We want to compare algorithms without tying ourselves to a specific machine, compiler, or input. A fast laptop running a bad algorithm will eventually lose to a slow one running a good algorithm — you just need a large enough input. So instead of measuring wall-clock time, we count how the number of primitive steps grows as the input grows.

Let n be the size of the input — the length of a vector, the number of nodes in a tree, the number of edges in a graph. A primitive step is anything that takes constant time regardless of n: an addition, a comparison, an array index, a pointer dereference.

int sum = 0;                    // 1 step
for (int i = 0; i < n; i++) {   // loop runs n times
    sum += v[i];                // 1 step per iteration -> n steps
}
return sum;                     // 1 step

This function performs roughly n + 2 steps. As n grows, the + 2 stops mattering. What matters is that the work grows linearly with n. We capture that with Big-O notation: this is O(n).

Asymptotic Notation

Asymptotic notation describes how a function behaves as its input tends to infinity. The three you will encounter:

• Big-O — $O(f(n))$ is an upper bound. The algorithm takes at most this much time.
• Big-Omega — $\Omega(f(n))$ is a lower bound. The algorithm takes at least this much time.
• Big-Theta — $\Theta(f(n))$ is a tight bound: both an upper and lower bound. The algorithm takes exactly this much time, up to constant factors.

In practice, "complexity" almost always means Big-O, because we care most about the worst case and the guarantee it gives us. This primer uses O-notation throughout, but keep in mind that when we say a loop "is O(n)" we usually mean it is tightly O(n) — that is, $\Theta(n)$.

The two rules that make it work

Big-O lets us throw away detail that doesn't affect the growth rate:

1. Drop constant factors. $O(2n)$, $O(100n)$, and $O(n/2)$ are all just $O(n)$. A constant multiplier doesn't change how the cost scales.
2. Drop lower-order terms. $O(n^2 + n)$ is $O(n^2)$. For large n, the $n^2$ term dominates so thoroughly that the $n$ is noise.

// 3n^2 + 5n + 10 steps  ->  O(n^2)
for (int i = 0; i < n; i++)        // the n^2 part dominates
    for (int j = 0; j < n; j++)
        do_work();                 // 3 constant ops here -> still O(1) each

Common Complexity Classes

These are the growth rates you will see again and again, from fastest to slowest:

The gap between these classes is enormous. For $n = 1{,}000{,}000$, an $O(n)$ algorithm does a million steps while an $O(n^2)$ algorithm does a trillion — the difference between instant and unusable.

Analyzing Iterative Code

Most analysis comes down to a few mechanical rules.

Sequential blocks add

When one block of work follows another, you add their costs — then drop the smaller one.

for (int i = 0; i < n; i++) do_work();   // O(n)
for (int j = 0; j < n; j++) do_work();   // O(n)
// total: O(n) + O(n) = O(2n) = O(n)

Nested loops multiply

When one loop runs inside another, you multiply their iteration counts.

for (int i = 0; i < n; i++)        // runs n times
    for (int j = 0; j < n; j++)    // runs n times for each i
        do_work();                 // O(1)
// total: n * n = O(n^2)

Watch the bounds carefully — they don't always multiply to the obvious answer:

for (int i = 0; i < n; i++)
    for (int j = i; j < n; j++)   // runs n + (n-1) + ... + 1 times
        do_work();
// total: n(n+1)/2 = O(n^2)  (the constant 1/2 drops)

Halving is logarithmic

When a loop divides the problem size each iteration instead of stepping through it, the count is logarithmic. You can only halve n about $\log_2 n$ times before reaching 1.

for (int i = n; i > 0; i /= 2)   // n, n/2, n/4, ..., 1
    do_work();
// total: O(log n)

Hidden loops count too

Standard-library calls are not free. A call inside your loop hides a loop of its own.

for (int i = 0; i < n; i++)
    if (std::find(v.begin(), v.end(), i) != v.end())  // std::find is O(n)
        do_work();
// total: n * O(n) = O(n^2)

Best, Average, and Worst Case

The same algorithm can take different amounts of time on different inputs of the same size. Consider linear search:

int find(const std::vector<int>& v, int target) {
    for (int i = 0; i < v.size(); i++)
        if (v[i] == target) return i;
    return -1;
}

• Best case — the target is the first element. One comparison: $O(1)$.
• Worst case — the target is last or absent. n comparisons: $O(n)$.
• Average case — over random inputs, about n/2 comparisons: still $O(n)$.

When a lecture says an operation "is O(n)" without qualification, it almost always means the worst case, because that is the guarantee you can rely on. The exceptions are operations described as "average" (like hash table lookups, which degrade to $O(n)$ in the worst case) and "amortized" — the subject of the next section.

Amortized Analysis

Some operations are usually cheap but occasionally expensive. Amortized analysis averages the cost over a long sequence of operations, so a rare expensive step is paid for by the many cheap ones around it. This is different from average case: amortized cost is a guarantee over any sequence, not an expectation over random inputs.

The canonical example is std::vector::push_back, which you met in Lecture 7.

std::vector<int> v;
for (int i = 0; i < n; i++)
    v.push_back(i);   // usually O(1); occasionally O(n) when it reallocates

When the vector runs out of capacity, it allocates a larger block (typically double the size) and copies every existing element over — that single push_back costs $O(n)$. But because the capacity doubles, those expensive copies happen rarely: at sizes 1, 2, 4, 8, 16, and so on.

Summing the copy work across n insertions gives $1 + 2 + 4 + \dots + n < 2n$ total copies. Spread over n calls, that's at most 2 copies per call — a constant. Hence amortized O(1) per push_back, even though a single call can spike to $O(n)$.

Analyzing Recursive Code

Loops are easy to count by inspection. Recursion needs a different tool: a recurrence relation, an equation that expresses the running time $T(n)$ in terms of the time on smaller inputs.

Start with a simple linear recursion:

int sum_to(int n) {
    if (n == 0) return 0;        // base case: O(1)
    return n + sum_to(n - 1);    // one recursive call on n-1, plus O(1) work
}

Each call does $O(1)$ work and makes one call on a problem of size n - 1. That gives the recurrence:

$T(n) = T(n - 1) + O(1)$

The substitution method

To solve a recurrence, unroll it until you reach the base case and look for the pattern:

$T(n) = T(n-1) + c = T(n-2) + 2c = T(n-3) + 3c = \dots = T(0) + nc$

After n unrollings we hit the base case, so $T(n) = O(n)$. The recursion is linear — which makes sense, since it's just a loop wearing a disguise.

Recursion that branches grows faster. Naive Fibonacci makes two calls per level:

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

This gives $T(n) = T(n-1) + T(n-2) + O(1)$, which unrolls into a call tree of roughly $2^n$ nodes — exponential, $O(2^n)$. That blow-up is exactly why we reach for memoization or dynamic programming.

The Master Theorem

Divide-and-conquer algorithms split a problem into equal-sized subproblems, solve them recursively, and combine the results. Their recurrences all share a shape, and the Master theorem solves that shape directly without unrolling.

For a recurrence of the form

$T(n) = a \, T(n/b) + f(n)$

where $a \ge 1$ subproblems each have size $n/b$, and $f(n)$ is the cost to split and combine, compare $f(n)$ against $n^{\log_b a}$:

The term $n^{\log_b a}$ measures the cost of all the leaves in the recursion tree; $f(n)$ measures the cost at the root. The theorem just asks which one dominates.

Worked examples

Binary search halves the input and does $O(1)$ work per level, so $a = 1$, $b = 2$, $f(n) = O(1)$:

int binary_search(const std::vector<int>& v, int target) {
    int lo = 0, hi = v.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (v[mid] == target) return mid;
        else if (v[mid] < target) lo = mid + 1;   // discard left half
        else hi = mid - 1;                         // discard right half
    }
    return -1;
}

Here $n^{\log_2 1} = n^0 = 1$, and $f(n) = O(1)$ matches it — Case 2 — giving $\Theta(\log n)$.

Merge sort splits into two halves and merges in linear time, so $a = 2$, $b = 2$, $f(n) = O(n)$:

void merge_sort(std::vector<int>& v, int lo, int hi) {
    if (lo >= hi) return;
    int mid = lo + (hi - lo) / 2;
    merge_sort(v, lo, mid);          // T(n/2)
    merge_sort(v, mid + 1, hi);      // T(n/2)
    merge(v, lo, mid, hi);           // O(n) to combine the two sorted halves
}

Here $n^{\log_2 2} = n^1 = n$, and $f(n) = O(n)$ matches it — Case 2 — giving the famous $\Theta(n \log n)$. The recursion tree makes this visible: each level does $O(n)$ total work, and there are $\log n$ levels.

Space Complexity

The same counting applies to memory. Space complexity measures how much extra memory an algorithm needs as a function of n, usually split into:

• Auxiliary space — extra memory beyond the input itself.
• Total space — auxiliary space plus the input.

Two common sources of space cost:

std::vector<int> doubled(const std::vector<int>& v) {
    std::vector<int> result;
    for (int x : v) result.push_back(x * 2);   // grows to size n
    return result;                              // O(n) extra space
}

Recursion costs space too: every pending call occupies a frame on the call stack. The sum_to function earlier reaches a recursion depth of n, so it uses $O(n)$ stack space even though it allocates nothing on the heap. Merge sort's recursion depth is $O(\log n)$.

This is the other axis of the array-vs-linked-list trade-off from Lecture 18: the time table there has a space companion, since pointers in a linked list cost memory that a contiguous array doesn't.

Cheat Sheet

Map the code pattern to its complexity at a glance:

Exercises

Q1.

State the worst-case time complexity of each snippet in Big-O notation, in terms of n.

// (a)
int total = 0;
for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        total += i * j;

// (b)
int count = 0;
for (int i = 1; i < n; i *= 2)
    count++;

// (c)
int sum = 0;
for (int i = 0; i < n; i++) sum += i;
for (int i = 0; i < n; i++) sum -= i;

// (d)
for (int i = 0; i < n; i++)
    if (std::binary_search(v.begin(), v.end(), i))
        do_work();

Q2.

The loop bound depends on the outer variable. Count the total number of times do_work() runs, then give the Big-O complexity.

for (int i = 0; i < n; i++)
    for (int j = 0; j < i; j++)
        do_work();

Q3.

Write the recurrence relation $T(n)$ for each recursive function, then solve it.

// (a)
int f(int n) {
    if (n <= 1) return 1;
    return f(n - 1) + 1;
}

// (b)
int g(int n) {
    if (n <= 1) return 1;
    return g(n / 2) + g(n / 2) + n;
}

Q4.

Apply the Master theorem to each recurrence. Identify a, b, f(n), the case, and the result.

(a) T(n) = 4T(n/2) + O(n)
(b) T(n) = T(n/2) + O(1)
(c) T(n) = 2T(n/2) + O(n^2)

Q5.

A colleague claims their function is $O(1)$ because "it's just one push_back in a loop." Explain in your own words why a single push_back can cost $O(n)$, yet a loop of n push_backs is still $O(n)$ overall and not $O(n^2)$.

Think about how often the vector reallocates, and how much each
reallocation copies.

Practice Problems

• Binary Search — Easy
• Two Sum — Easy
• Merge Intervals — Medium