Growth rates and Big-O

From exact counts to growth

The previous lesson ended with exact step counts such as n(n − 1)/2. Exact counts are more detail than you need. Take a function that does 3n² + 5n + 20 steps. At n = 1,000 that is 3,000,000 + 5,000 + 20 = 3,005,020 steps, and the n² term accounts for 99.8% of them. At a million, the other terms are a rounding error.

The constant in front, the 3, matters even less for choosing an algorithm. It changes with the language, the compiler and the machine, while the n² is a property of the algorithm itself. Double n, and any n² algorithm does four times the work, whatever its constant.

So the useful summary of a step count is its fastest-growing term, without its constant. That summary is what Big-O notation writes down: 3n² + 5n + 20 is O(n²).

What O(f(n)) means

Formally, a step count T(n) is O(f(n)) if there are constants c and n₀ such that T(n) ≤ c × f(n) for every n ≥ n₀. In words: beyond some input size, the count never exceeds a constant multiple of f(n). For 3n² + 5n + 20, c = 4 works for every n ≥ 8, so the count is O(n²).

Two details of that definition explain how Big-O behaves:

• It is an upper bound. Strictly, a linear algorithm is also O(n²), because n ≤ n² for n ≥ 1. Textbooks use Ω (omega) for lower bounds and Θ (theta) when both bounds match. In practice, and in interviews, "O(n)" is used to mean the tight bound, and that is how this track uses it.
• It describes large n only. The definition starts at some n₀ and says nothing about small inputs. That is why constants can still decide which algorithm wins on small data.

The common growth rates

A few growth rates cover almost every algorithm you will meet. The trace above shows four of them side by side.

The first four are the everyday ones, and the jump from O(n log n) to O(n²) is where programs stop scaling: in the trace, a million items cost 20 million steps one way and a trillion the other. Exponential and factorial algorithms are only usable for tiny n, and much of the advanced level of this track is about avoiding them.

A logarithm counts how many times you can halve n before reaching 1, which is why it barely grows: 10 for a thousand, 20 for a million, 30 for a billion. The base doesn't matter in Big-O, because logarithms in different bases differ by a constant factor.

Will it finish in time?

Combine the growth rate with the rule of thumb from the last lesson, roughly a billion simple steps per second in compiled code, and you can estimate the largest input an algorithm can handle within about a second:

Read the table the other way and it tells you which algorithm a problem needs. Coding interviews and programming contests state limits such as "n ≤ 100,000" precisely so you can do this: with 100,000 items, an O(n²) solution does 10¹⁰ steps and won't finish, so an O(n log n) or O(n) one is expected.

Rules for combining

A few rules let you work out the Big-O of a whole function from its parts, without writing out the full count:

• Sequential parts add, and the largest wins. A loop that is O(n) followed by one that is O(n²) is O(n + n²), which is O(n²).
• Nested parts multiply. An O(n) loop whose body does O(log n) work, such as a binary search, is O(n log n).
• Constants disappear. Ten passes over the data are O(10n), which is O(n). So is one pass that does ten things per element.
• Separate inputs stay separate. Comparing every element of a list of size n with every element of a list of size m is O(n·m).

These rules are why a single line that hides a loop matters so much: it can turn an O(n) function into an O(n²) one by being nested where you didn't see a loop.

When constants win

Big-O decides what happens as n grows, but real inputs have a size, and for small sizes constants can win. Compare 1,000n with n²/1,000: the quadratic one is cheaper until n reaches a million.

Real libraries rely on this. Sorting functions such as Python's and Java's switch to insertion sort, an O(n²) algorithm, for small pieces of an array, because for a few dozen elements its tiny constant and cache-friendly access beat the overhead of an O(n log n) method. And as the first module showed, cache misses can make one O(n) loop ten times slower than another.

So use Big-O to rule out algorithms that can't scale, then measure among the ones that remain. The next lesson adds one more dimension: the same algorithm can take very different numbers of steps on different inputs of the same size.

Pseudocode & Multi-Language Implementations (C++, Java, Python)

To translate Growth rates and Big-O from mental model into production and interview code, start from the language-independent pseudocode below and compare how C++, Java, and Python express the exact same loop invariant:

log2(n)       # rate 0: binary search
n             # rate 1: one pass over the data
n * log2(n)   # rate 2: a good sort
n * n         # rate 3: every pair

#include <vector>
#include <algorithm>
 
long long processArrayInvariants(std::vector<int>& nums) {
    long long acc = 0;
    int lo = 0, hi = static_cast<int>(nums.size()) - 1;
    while (lo <= hi) {
        acc += nums[lo];
        if (lo < hi) acc += nums[hi];
        ++lo; --hi;
    }
    return acc;
}

public class ArrayInvariantSolver {
    public static long processArrayInvariants(int[] nums) {
        long acc = 0;
        int lo = 0, hi = nums.length - 1;
        while (lo <= hi) {
            acc += nums[lo];
            if (lo < hi) acc += nums[hi];
            lo++; hi--;
        }
        return acc;
    }
}

def process_array_invariants(nums: list[int]) -> int:
    acc = 0
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        acc += nums[lo]
        if lo < hi:
            acc += nums[hi]
        lo += 1
        hi -= 1
    return acc

Complexity Derivation, Edge Cases & Common Mistakes

• Time & Space Complexity Derivation: Always count how many times the inner state advances relative to input size n (amortized pointer movements, tree height O(log n), or hash-table load factor < 1) and distinguish auxiliary space (extra stack frames or buffers allocated by your algorithm) from the input storage itself.
• Boundary & Edge Cases to Verify: Test empty or single-element inputs (n <= 1), all-duplicate values, already-sorted and reverse-sorted sequences, disconnected components, and 32-bit signed integer limits (2^31 - 1) where intermediate sums or index products require 64-bit long long / long.
• Common Beginner Mistakes: Avoid recomputing prefix/window state from scratch inside nested loops, mutating a container while iterating over it, or forgetting base-case termination guards before dereferencing pointers or indices.