Math for coding interviews/n log n - the sweet spot
O(n log n): Why Merge Sort Beats Bubble Sort
n log n sits between n (linear) and n² (quadratic). For n=1000: n=1000, n log n≈10,000, n²=1,000,000. Merge sort achieves n log n by dividing the array in half log(n) times and doing n work at each level.
See it for yourself
Three curves on the same graph. n is a gentle diagonal. n log n is slightly steeper but still gentle. n² curves upward steeply. For large inputs the gap between n log n and n² is enormous.
n log n - the sweet spot
n log n sits between n (linear) and n² (quadratic). For n=1000: n=1000, n log n≈10,000, n²=1,000,000. Merge sort achieves n log n by dividing the array in half log(n) times and doing n work at each level.
Think of it this way: Sorting a deck of cards by splitting it in half, sorting each half, then merging. Each split takes constant work per card. Because you only split log(n) times, the total is n log n.
For algorithms: Comparison-based sorting cannot do better than O(n log n). Bubble/insertion sort are O(n²). Merge sort and heapsort hit the theoretical minimum of n log n.
Real-world analogy
Sorting a deck of cards by splitting it in half, sorting each half, then merging. Each split takes constant work per card. Because you only split log(n) times, the total is n log n.
Why it matters in interviews
Comparison-based sorting cannot do better than O(n log n). Bubble/insertion sort are O(n²). Merge sort and heapsort hit the theoretical minimum of n log n.