What is O(log n)?

A logarithm is like counting how many times you need to divide a number by 2 until it becomes small, and O(log n) means something gets faster as the problem size grows, just like finding a toy in a box with clever clues.

Imagine you have a big box of toys. If you look through them one by one, that’s like checking each toy, linear time, or O(n). But what if you had clever clues?

Let’s say the box is sorted from smallest to largest toy. You pick the middle toy and check it. If your toy is smaller, you only need to search the left half of the box next time. If it's bigger, you look at the right half. Each time, you cut the problem in half, that’s like taking a big pile of toys and splitting them into two smaller piles.

This is logarithmic growth, every time you double the number of toys, you only need one more step to find your toy. So if there are 8 toys, it takes 3 steps; with 16, it takes 4. The bigger the box, the slower it grows, like climbing stairs that get less steep as you go up.

That’s O(log n) in action: smart searching, cutting work in half each time!