Let's say we have m queries. Amortized cost per query would be \frac{O(n log n) + m * O(log n)}{m}. When m in O(n), it would be O(log n).
isalinas
Put more simply, the up-front cost of sorting becomes smaller every time we perform a search. If we're performing a few searches, then sort+binary search is more expensive than brute force search. But once we have to perform millions of queries, the cost of searching repeatedly overwhelms the cost of performing the sort just once, until we can effectively ignore that cost.
Why is amortized cost over many queries O(log n)?
Let's say we have m queries. Amortized cost per query would be \frac{O(n log n) + m * O(log n)}{m}. When m in O(n), it would be O(log n).
Put more simply, the up-front cost of sorting becomes smaller every time we perform a search. If we're performing a few searches, then sort+binary search is more expensive than brute force search. But once we have to perform millions of queries, the cost of searching repeatedly overwhelms the cost of performing the sort just once, until we can effectively ignore that cost.