When you first learn about Binary Search, the explanation usually goes something like this: "We look at the middle of the sorted array. If it's not our target, we throw away half the array and repeat."
It's an incredibly efficient strategy. But if you sit down and try to map that action to Big-O notation, an intuitive trap opens up:
"If we are breaking the array in half, shouldn't the time complexity be O(n/2)?"
If you’ve ever had this thought, you aren't alone. Today, let's look past the generic "just memorise the cheat sheet" advice and break down the exact math of why repeated halving completely changes the growth class of your code.
1. The Flaw in O(n/2)
