Neel Mishra
← All Posts
DSA Series · Complexity · Part 7

Why Logarithms Appear

March 2026 · 16 min read

$O(\log n)$ appears more often than any other sub-linear complexity. It's not a coincidence, there's a single underlying principle that explains all of it.

The Halving Principle

The Rule: If each step eliminates a constant fraction of the remaining work, the total number of steps is $O(\log n)$.

Start with $n$. After step 1: $n/2$. After step 2: $n/4$. After step $k$: $n/2^k$. We stop when $n/2^k \leq 1$:

$$\frac{n}{2^k} = 1 \implies 2^k = n \implies k = \log_2 n$$

This is the mathematical reason $\log n$ appears. Every time you halve, you get a log.

Start with $n$ elements. Each comparison eliminates half. After $k$ comparisons, $n/2^k$ elements remain.

$$n/2^k = 1 \implies k = \log_2 n$$

This is the purest example of the halving principle. Binary search is repeated halving.

What if it's not exactly half?

Suppose each step eliminates at least $1/3$ of the elements (worst case in ternary search, or unbalanced binary search). After $k$ steps, at most $\frac{2}{3}^k \cdot n$ remain:

$$\left(\frac{2}{3}\right)^k \cdot n = 1 \implies k = \log_{3/2} n = \frac{\ln n}{\ln(3/2)} = O(\log n)$$

Any constant fraction leads to $O(\log n)$. The base changes but is absorbed into the constant.

Balanced Trees

A balanced binary tree with $n$ nodes has height $h = \Theta(\log n)$. Why?

A perfectly balanced binary tree of height $h$ has at most $2^{h+1} - 1$ nodes. So $n \leq 2^{h+1} - 1$:

$$h \geq \log_2(n + 1) - 1 = \Omega(\log n)$$

And since balancing guarantees $h = O(\log n)$, operations that traverse root-to-leaf (search, insert, delete) take $O(\log n)$.

BST, AVL, Red-Black, B-trees

All these maintain balance invariants that keep the height at $O(\log n)$. The specific constant differs (AVL is stricter than Red-Black), but the $\log n$ factor is the same.

Divide and Conquer

Divide-and-conquer splits the problem into smaller subproblems. The number of split levels is $\log n$ (since each level halves the problem size).

Number of Digits

The number of digits in $n$ (in base $b$) is $\lfloor \log_b n \rfloor + 1 = \Theta(\log n)$. This is why algorithms that process digits (radix sort, number-theoretic algorithms) have $\log n$ in their complexity.

Bits and Representation

To represent $n$ distinct values, you need $\lceil \log_2 n \rceil$ bits. This is the information-theoretic lower bound for distinguishing $n$ outcomes.

Binary search achieves this: it needs $\lceil \log_2 n \rceil$ comparisons (yes/no questions) to find one element among $n$. Each comparison provides 1 bit of information.

Exponentiation by Squaring

long long power(long long base, int exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp % 2 == 1) result = result * base % mod;
        exp /= 2;            // halving!
        base = base * base % mod;
    }
    return result;
}

The exponent is halved at each step. Number of iterations: $\lfloor \log_2(\text{exp}) \rfloor$. This computes $a^n \mod m$ in $O(\log n)$ multiplications instead of $O(n)$.

Why the Log Base Doesn't Matter

The change of base formula:

$$\log_a n = \frac{\log_b n}{\log_b a}$$

The factor $\frac{1}{\log_b a}$ is a constant (independent of $n$). So:

$$O(\log_a n) = O\left(\frac{\log_b n}{\log_b a}\right) = O(\log_b n)$$

In Big-O, all logarithm bases are equivalent. We simply write $O(\log n)$.

Summary