O(log n): Logarithmic Time
You'll learn how logarithmic time complexity describes algorithms that become only slightly slower as input grows dramatically.
The Core Idea
An algorithm runs in O(log n) time when it repeatedly cuts the problem size in half (or into some constant fraction) with each step. This means doubling the input size only adds one more step to the process.
Think of it like finding a name in a phone book. Instead of reading every name, you open to the middle, decide if your target is in the left or right half, discard the other half, and repeat. Each step eliminates half the remaining names.
Binary Search: The Classic Example
Binary search is the poster child for O(log n) complexity. When searching a sorted array:
- Step 1: Check the middle element
- Step 2: If your target is smaller, search the left half; if larger, search the right half
- Repeat: Keep halving the search space until you find the target or run out of elements
With 1,000 elements, binary search needs at most ~10 comparisons. With 1,000,000 elements? Only ~20. That's the power of logarithmic growth.
Why "log n"?
The "log" (logarithm) answers: "How many times must I divide n by 2 to reach 1?" For n = 8: 8 → 4 → 2 → 1 (3 divisions, log₂(8) = 3).
When You See O(log n)
Any algorithm that repeatedly halves, quarters, or divides the problem by a constant factor typically exhibits logarithmic time:
- Binary search in sorted arrays
- Finding elements in balanced binary search trees
- Certain divide-and-conquer algorithms
Key Takeaway: O(log n) algorithms scale beautifully—they remain fast even with massive inputs because each step drastically reduces the remaining work.