9. Analyzing Logarithmic Time: O(log N)

O(log N) is extremely efficient. It means that as the input size (N) grows, the number of operations needed grows very slowly.

What is Logarithmic Growth?

Logarithmic algorithms work by continually dividing the problem size in half (or some fraction) at each step. If you have 1024 items, you only need 10 steps to reduce the problem to size 1 (since 2^10 = 1024).

The Power of O(log N)

• N = 1,000,000
• O(N) = 1,000,000 operations.
• O(log N) ≈ 20 operations.

Example: Binary Search

The most famous example is Binary Search (covered in detail later). If you are looking for a name in a massive, alphabetized phonebook, you open it to the middle. You immediately eliminate half the book. You repeat this process, cutting the remaining problem space in half until you find the name.