Why Repeatedly Halving an Array is O(log n), Not Linear

Deep Coomer — Thu, 25 Jun 2026 08:11:50 +0000

When you first learn about Binary Search, the explanation usually goes something like this: "We look at the middle of the sorted array. If it's not our target, we throw away half the array and repeat."

It's an incredibly efficient strategy. But if you sit down and try to map that action to Big-O notation, an intuitive trap opens up:

"If we are breaking the array in half, shouldn't the time complexity be O(n/2)?"

If you’ve ever had this thought, you aren't alone. Today, let's look past the generic "just memorise the cheat sheet" advice and break down the exact math of why repeated halving completely changes the growth class of your code.

1. The Flaw in O(n/2)

The immediate, "textbook" answer to this question is that Big-O notation ignores constant multipliers. Because of this, O(n/2) isn't actually a distinct category:

O(n/2) = O(1/2 * n) = O(n)

An O(n/2) algorithm is still linear. If your dataset grows from 1,000 to 1,000,000 items, a linear algorithm's operations scale proportionally by 1,000x.

But when we search a sorted array by halving it, we aren't just dividing the work into two piles and scanning one entire pile. We are repeating the division process at every single step.

2. The Logic of Repeated Halving

Let's step away from the abstract formulas and look at a concrete example. Imagine we have a sorted array of 8 elements, and we are looking for a specific number.

Every time we check the middle element and miss, the search space shrinks:

Step 0: We start with 8 elements.
Step 1: First cut -> 4 elements left.
Step 2: Second cut -> 2 elements left.
Step 3: Third cut -> 1 element left (we either found it or it's not there).

[ 1, 2, 3, 4, 5, 6, 7, 8 ]  -> Step 0 (Size: 8)
      [ 5, 6, 7, 8 ]        -> Step 1 (Size: 4)
         [ 7, 8 ]           -> Step 2 (Size: 2)
           [ 8 ]            -> Step 3 (Size: 1)

It exactly took us 3 steps to reduce 8 elements down to 1.

3. Connecting the Dots to Logarithms

How do we mathematically describe the relationship between our starting size (8) and the number of steps it took to get to one (3)?

We are asking: "How many times do we need to multiply 2 by itself to reach 8?"

2 x 2 x 2 = 2^3 = 8

The inverse of an exponent is a logarithm. Specifically, a base-2 logarithm (log_2) answers the exact opposite question: "How many times do I have to divide this number by 2 to get down to 1?"

log_2(8) = 3

If we scale this up to an array of any size n, the number of steps k required to finish the search follows this formula:

n/2^k = 1 => n = 2^k => k = log_2(n)

4. Why Big-O Drops the Log Base

You might wonder why we write O(log n) instead of O(log_2 n), especially since we are dividing by 2. In computer science, base-2 is the default assumption, but mathematically, the base actually doesn't change the Big-O classification.

Thanks to the Change of Base rule, converting a base-2 log to a standard base-10 log looks like this:

log_2(n) = log_10(n) / log_10(2) ≈ 3.32 * log_10(n)

Because log_10(2) is just a constant number (≈ 0.301), log_2(n) and log_10(n) differ only by a constant multiplier (3.32).. Just like dropping the 1/2 from O(n/2), Big-O drops this multiplier too:

O(log_2 n) = O(3.32 * log_10 n) = O(log_n)

Whether you are dividing your data into 2 parts (Binary Search) or 10 parts (like a 10-way B-Tree search), the algorithm scales at the exact same logarithmic rate.

Summary Comparison

Concept	Mechanics	Big-O Class	Scaling Behavior
O(n/2)	A single scan over exactly half of the data.	O(n) (Linear)	If data doubles, execution time doubles.
O(\log n)	Data is repeatedly cut in half at every step.	O(\log n) (Logarithmic)	If data doubles, you only add one extra step.

The Ultimate Perspective:
If you have a sorted array of 1,000,000 elements:

A linear O(n/2) approach takes 500,000 operations.

A logarithmic O(\log n) approach takes roughly 20 operations.

The next time someone tells you an algorithm is efficient because it "cuts the problem in half," remember that the magic isn't in the first cut—it's in the power of the repeated cut.