The Halving Pattern (Where log n comes from)

$O(\log n)$ appears whenever you repeatedly divide the problem size by a constant factor. The most common pattern is halving.

Start with $n$ items. After one step, you have $\frac{n}{2}$. After two steps, $\frac{n}{4}$. After three steps, $\frac{n}{8}$. After $k$ steps, you have $\frac{n}{2^k}$ items left.

You stop when you reach $1$ item, meaning $\frac{n}{2^k} = 1$. Solving for $k$: $2^k = n$, so $k = \log_2(n)$. That's where the logarithm comes from.