O(log n)

What it means

O(log n) means the work grows very slowly compared with the input size.

That usually happens when each step removes a large part of the remaining problem.

Common shape

The classic example is binary search.

You do not scan item by item.

You inspect the middle and decide which half is still relevant.

When it matters

O(log n) often appears when:

• the data is ordered
• you can discard half the search space each step
• the next decision depends on the current result

Better question

Instead of memorizing “binary search is O(log n),” ask:

1. can I remove half the problem each step?
2. does the data shape allow that without breaking the logic?
3. is the input already ordered, or do I pay that cost first?