Algorithms and Data Structures · Senior · Question 30 of 75
Why can an O(n log n) algorithm lose to an O(n²) one on real inputs?
- ✓Correct answer: Big O hides constants, and for small n they dominate
- 2O(n²) algorithms are compiled with more optimizations
- 3O(n log n) only holds when n is a power of two
Explanation
Insertion sort beats merge sort below a few dozen elements thanks to tiny overhead and cache-friendly access. That's why Timsort and introsort switch to insertion sort for small runs.