What Does O(log n) Mean Exactly?

O(log n) describes the time complexity of an algorithm, indicating its efficiency. It means that as the input size $n$ grows, the algorithm’s runtime increases logarithmically. Specifically, the runtime is proportional to the logarithm of $n$, typically base 2 (log₂).

This behavior is common in divide-and-conquer algorithms like binary search, where the input size is halved at each step. For example, searching in a sorted list of 1,000,000 elements takes about 20 steps in binary search (log₂(1,000,000) ≈ 20).

O(log n) is efficient, as it grows much slower than linear (O(n)) or quadratic (O(n²)) time complexities.