What a comparison is worth: the log from first principles

Suppose you must identify one number from one to a million using only yes/no questions. How many questions do you need? About twenty. Not a million. Not a hundred thousand. Twenty. Binary search uses the same trick: each answer halves the possibilities, and about twenty halvings reduce a million possibilities to one. One comparison is worth one bit. That is why the log appears throughout this site’s complexity claims, and this is where the claim comes from. It is the sibling of the binary trees article: there, the log in $O(\log n)$ comes from a tree’s levels, a structural fact about forking; here, it comes from the answers to your questions, an informational fact about what you still do not know. If the notation is new, read What O(n) actually promises first.

The guessing game

The million-number game is an information puzzle, and its math is the whole argument. Start with $N$ possibilities. Ask a yes/no question: “is it bigger than 500,000?” The answer selects one of two sets. Ask well, and each answer at least halves the remaining set. After one question, at most $N/2$ candidates remain; after two, at most $N/4$; after $k$ questions, at most $N / 2^k$. Once that number drops below 1, you must have found the answer. So you need the smallest $k$ such that $N / 2^k \le 1$. That is the same as $2^k \ge N$, which is what the logarithm means: $k = \log_2 N$.

That is the relationship. The numbers make it concrete. A million candidates need $\log_2 1{,}000{,}000 \approx 20$ questions. A billion needs about thirty. A trillion needs about forty. The list grows by a factor of a thousand while the questions grow by ten: adding three zeros to the problem adds about ten questions, because adding one zero to $N$ adds $\log_2 10 \approx 3.3$ questions. Three zeros add about ten. Exponential growth in the input becomes linear growth in the questions. That is what “grows like a log” means.

Information theory calls a yes/no answer one bit. That term matters here. A question with two possible answers carries one bit of information. The word “bit” here is not the storage unit from the site’s bits-have-no-meaning article, though the two are the same coin: the stored-program bargain says a bit is a physical thing you can flip; information theory says a bit is an answer you did not have. The guessing game gives the exchange rate. Identifying one of $N$ possibilities requires $\log_2 N$ bits of information, and each yes/no question buys one.

Binary search is the guessing game

Binary search is the guessing game with bookkeeping. The site’s Binary Search problem gives you a sorted array and a target. The algorithm compares the target with the middle element. That comparison is the question. If the target is smaller, it can only be in the left half; if larger, only in the right. Each comparison halves the remaining window. The sorted order makes “half” meaningful: the algorithm does not need to look at the elements, only compare them. The classic introduction states the cost alongside the method: “In general, for any list of $n$, binary search will take $\log_2 n$ steps to run in the worst case, whereas simple search will take $n$ steps.”

“Steps” means comparisons, and the claim is measurable. A million-element array takes about twenty comparisons in the worst case, no matter where the target sits. The Elixir below is the site’s own solution with a counter added, so the cost is visible:

defmodule Search do
  @doc "Returns {index, comparisons} - the cost of finding target in sorted nums."
  def find(nums, target) do
    search(nums, target, 0, length(nums) - 1, 0)
  end

  defp search(_nums, _target, left, right, comparisons) when left > right,
    do: {-1, comparisons}

  defp search(nums, target, left, right, comparisons) do
    middle = div(left + right, 2)
    value = Enum.at(nums, middle)
    comparisons = comparisons + 1

    cond do
      value == target -> {middle, comparisons}
      value < target -> search(nums, target, middle + 1, right, comparisons)
      true -> search(nums, target, left, middle - 1, comparisons)
    end
  end
end

nums = Enum.to_list(1..1_000_000)

Search.find(nums, 999_999)
# => {999_998, 19}  - the worst case, nineteen comparisons
Search.find(nums, 500_000)
# => {499_999, 1}   - the middle, one comparison

Nineteen comparisons identify one position in a million. The problem description adds the detail that makes the cost fragile: “the one-element window is where boundary bugs go to hide.” Halving works only when the window math is exact. If the middle is off by one, the algorithm can compare forever inside a window that refuses to shrink. The guessing game is easy to describe and exact to implement. That is why the exercise exists.

What a comparison is worth

The guessing game and binary search use the same argument. It has a general form. A comparison-based algorithm can learn about its input only by comparing elements, and each comparison asks a question whose answer the algorithm does not control. As a decision, a comparison has at most two relevant outcomes: “go left” or “go right.” After $k$ comparisons, the algorithm can be in at most $2^k$ states. To do a job with $N$ possible answers - find one of $N$ positions, produce one of $N$ orderings - it must reach $N$ different states. Therefore $2^k \ge N$: no comparison-based algorithm can finish a job with $N$ possible outcomes in fewer than $\log_2 N$ comparisons. The information has to come from somewhere, and each comparison supplies one bit.

Here is the point: the log is the price of ignorance. You pay one comparison for each bit you do not have. If the input has structure you can use - sortedness, hashing, indexing - you pay less, sometimes nothing, because the information was already there. If the input is opaque and comparison is your only tool, you pay the log for every distinction the job requires. No cleverness changes that bill. Binary search halves the candidates not because halving is a special property of the algorithm, but because distinguishing one position in $n$ has a minimum price.

The sorting wall, same argument

The same bill appears in sorting. That is why the site’s sorting article has a wall at $n \log n$. Sorting is the guessing game with $n!$ possible answers. A comparison sort must distinguish every possible ordering because any one of them could be the input. There are $n!$ orderings, so it needs at least $\log_2(n!)$ bits. Since $n!$ grows so quickly, $\log_2(n!)$ is roughly $n \log_2 n$ (the sorting article derives that shape, and its wall section is the full argument). The concrete number makes the limit clear: for just 50 elements, $\log_2(50!) \approx 214$, so any comparison sort must use at least 214 comparisons on some input of size 50, no matter how clever it is. The cleverest sort in the world cannot go below that floor. It is the same information floor as the guessing game: $n!$ answers, one bit per comparison.

The geometry of elimination

The principle becomes useful when you ask what one bit can eliminate. The comparison is always one bit, but what one bit buys depends on the candidate set. Binary search has a one-dimensional candidate set: a window of positions. One bit halves it, so $n$ positions cost $\log_2 n$. The site’s Two Sum II problem applies the same accounting to a two-dimensional set. The input is a sorted array and the answer is a pair of positions, so there are $n^2$ candidate pairs. Sorted order lets each comparison remove a whole row or column. Compare the two ends. If their sum is too small, the left element is too small to pair with anything, so every pair involving it is dead: $n$ candidates disappear in one comparison. If the sum is too big, the right element is too big to pair with anything, and the same thing happens on the other side. The algorithm walks inward and touches each element once, so $n$ comparisons retire all $n^2$ pairs. Each bit buys $n$ candidates instead of 2 because sorted order gives the comparison power over a whole dimension. Same principle, different geometry: one bit per comparison, and the problem’s structure determines what a bit is worth.

The geometry can also remove the log. The reason is the same. The wall binds only algorithms whose only tool is comparison. A counting sort or radix sort never compares; it uses the values themselves as array indices. The “one bit per comparison” accounting does not apply, so the $n \log n$ floor falls. The sorting article’s escape-hatch section tells that story. Here is the point: when an algorithm stops asking yes/no questions about elements and starts using what the elements are, the information is no longer paid for per bit because the structure was already in the data.

The practical read

On a problem page, read the notation as a story about questions. $O(\log n)$ means “this algorithm asks about twenty questions of an input of a million - it halves per step.” $O(n)$ means “it looks at everything once - it has no halving to exploit.” $O(n \log n)$ means “it halves, but it must do so for every element” - the sort pays the log per item because every item’s final position is one of $n$ answers. The What O(n) article gives the shapes; this article gives the reason those shapes exist. The reason is always the same: the job has a certain number of possible answers, and each comparison is one bit toward separating them. The Algorithms past the interview article calls the skill of naming a bound before an interviewer does the class-recognition move; this is the accounting that makes the names meaningful instead of memorized.

Where to go next

• Binary Search - the guessing game with bookkeeping: implement the exact halving, and meet the one-element window where the boundary bugs hide.
• Two Sum II - the two-dimensional version: the sorted order makes each comparison retire a whole row or column, so the pair search costs $O(n)$, not $O(n^2)$.
• Merge Sort - the $n \log n$ face of the log: the sort that pays the log once per element because every element’s position is one of $n$ answers.
• Binary trees: where the log in O(log n) lives
  • the structural sibling: the same log as tree height, the same log as comparison count.
• Sorting: the wall at n log n
  • the full derivation of the wall this article states in one number: $\log_2(50!) \approx 214$.
• What O(n) actually promises - the growth shapes this article’s halving argument explains from the ground up.
• Bits have no meaning - the stored bit and the information bit are the same coin; the guessing game is the exchange rate between them.

One comparison is one bit, and the log is the number of bits you must spend. That is the whole argument. A job with $N$ possible answers costs $\log_2 N$ comparisons for any algorithm that learns only by comparing. The cleverness is not in avoiding the bill, but in shaping what one bit buys: a half, a row, or nothing when the data already knew the answer. The guessing game is complexity theory in miniature: twenty questions for a million, because a million is a twenty-bit answer, and a comparison is a bit.