Math behind big O: logarithms, powers and growth rates

← Back to the section

The whole section compares algorithms with big O notation: O(1), O(N), O(log N), O(N²). Behind those symbols hides very little math — powers, logarithms and the idea of "how fast a function grows". Most of it was taught at school and then never used again for years. This article is a short refresher from zero, so that log N and N² read without stumbling later on.

Powers: N squared and two to the power of N

A power is shorthand for multiplying a number by itself. N² ("N squared") is N × N, N³ is N × N × N, and N to the power of k is N multiplied by itself k times.

The difference between N² and 2ⁿ is fundamental, even though at N = 10 the numbers look close (100 against 1024). The easiest way to see it is to compute both as N grows:

live example

public class Growth {
    public static void main(String[] args) {
        for (int n = 10; n <= 30; n += 10) {
            System.out.println("N=" + n + "  N squared = " + (long) n * n + "  2^N = " + (1L << n));
        }
    }
}

At N = 30 the square is 900 — still nothing. Two to the power of 30 is already a billion.

• In N² the base grows while the exponent is fixed (two). Double the data and the work grows fourfold. That is quadratic growth: fast, but predictable.
• In 2ⁿ the base is fixed (two) and the exponent grows — N itself. Every extra element doubles the result. That is exponential growth, and it explodes: at N = 30 it is already over a billion, at N = 60 it is more than the number of seconds since the Big Bang.

Logarithms: the other side of a power

A logarithm answers the reverse question. A power asks: "what is 2 to the power of 3?" (answer: 8). A logarithm asks the opposite: "to what power must 2 be raised to get 8?" (answer: 3). It is written log₂ 8 = 3.

For algorithms a different definition of the same thing is handier:

log₂ N is how many times N has to be halved to reach 1.

Two consequences follow:

• A logarithm grows very slowly. Data grew a thousandfold — the number of halvings went up by only 10 (log₂ 1000 ≈ 10, because 2¹⁰ = 1024). For a million log₂ 1 000 000 ≈ 20, for a billion it is 30. That is why an algorithm running in log N barely notices the data growing.
• The base of the logarithm does not matter for big O. log₂ N and log₁₀ N differ only by a constant factor, and constants are dropped in big O. That is why people simply write O(log N) without naming the base.

You can check that by plain counting: halve the number until it reaches 1 and count the steps.

live example

public class Halvings {
    public static void main(String[] args) {
        for (long n : new long[]{16, 1024, 1_048_576}) {
            long value = n;
            int steps = 0;
            while (value > 1) {
                value /= 2;
                steps++;
            }
            System.out.println(n + ": halvings = " + steps);
        }
    }
}

A million and change takes twenty steps. Estimating log₂ N in your head is easy too: it is the number of binary digits minus one, that is, the logarithm rounded down. Three landmarks are worth memorising: log₂ 1000 ≈ 10, log₂ 1 000 000 ≈ 20, log₂ 1 000 000 000 ≈ 30.

How fast different functions grow

The whole point of big O is how a function behaves when N gets large. Here are the main growth rates from the slowest to the fastest, with their values at N = 10, 100 and 1000:

The gap between the rows is the difference between "instant" and "never finishes". On a thousand elements a logarithm is 10 steps and a square is a million; on a million the gap is already a hundred thousand times.

How big O is read off a formula

Big O takes the formula for the number of operations and keeps only the part that decides how it grows on large N. There are two rules:

1. Drop constants and factors. 3N and 100N are both O(N): twice the data means twice the work, the coefficient does not matter.
2. Keep the fastest growing term. In the sum N² + N + 100 everything is decided by N² when N is large: at N = 1000 that is 1 000 000 + 1000 + 100, and the smaller terms vanish. So it is O(N²).

Why so crude? Because big O answers not "how many milliseconds" but "what happens once there is a lot of data". On small N every algorithm is fast; the difference shows up on large ones.

In short

• A power N² is N×N (quadratic growth: double the data, four times the work). 2ⁿ is two multiplied by itself N times (exponential, explosive growth).
• A logarithm log₂ N is how many times N is halved to reach 1. It grows very slowly: a million is ~20, a billion is ~30. The base does not matter for big O.
• Growth rates in order: 1 < log N < N < N·log N < N² < 2ⁿ. On large N the gap between them is enormous.
• Big O is read like this: drop constants and factors, keep the fastest growing term. 3N² + 5N + 9 → O(N²).
• N·log N is almost linear. On a million elements it costs only 20 times more than N and 50 000 times less than N².
• The measure is about large N. On a hundred elements everything is fast; the gap between O(N) and O(N²) appears as the data grows — which is why constants are dropped.

What to read next

• Arrays, binary search and big O — where this math first pays off: why binary search is O(log N).
• Recursion — divide and conquer, the source of N·log N in the fast sorting algorithms.
• Advanced sorting — how algorithms move from O(N²) to O(N·log N).
• Choosing a data structure — where these estimates turn into a decision.