Math for coding interviews/Logarithms - "how many times can you cut in half?"
Logarithms Explained by Cutting in Half
log₂(n) answers this question: if you start with n things and keep cutting the group in half, how many cuts until you reach 1? For 1,024 items that is only 10 cuts. For a million items it is about 20. The number barely grows even as n explodes.
See it for yourself
Picture a tree branching downward. The top level is all n items. Each level below is half the size. The number of levels in that tree is log₂(n).
Logarithms - "how many times can you cut in half?"
log₂(n) answers this question: if you start with n things and keep cutting the group in half, how many cuts until you reach 1? For 1,024 items that is only 10 cuts. For a million items it is about 20. The number barely grows even as n explodes.
Think of it this way: A phone book with 1,024 names. Flip to the middle - is your name before or after? Flip to the middle of the surviving half. Repeat. You find any name in at most 10 flips, not 1,024.
For algorithms: Any algorithm that cuts its remaining work in half each step runs in O(log n). Binary search, balanced tree lookups, and heap operations all work this way.
Real-world analogy
A phone book with 1,024 names. Flip to the middle - is your name before or after? Flip to the middle of the surviving half. Repeat. You find any name in at most 10 flips, not 1,024.
Why it matters in interviews
Any algorithm that cuts its remaining work in half each step runs in O(log n). Binary search, balanced tree lookups, and heap operations all work this way.