Course contentsShow
← Computer Science
Lesson 284 of 2,8727. Introduction to Complexity AnalysisFree lesson

O(log n): Logarithmic Time

Understanding logarithmic complexity through binary search and algorithms that halve the problem size each step.

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.