What does O(n log n) versus O(n²) actually mean in practice?
- Expert answer
- Undergraduate
- Asked
The question
For an algorithms coursework I need to justify choosing merge sort over bubble sort. I can quote the Big O values, but I have been asked to explain why the difference matters for real input sizes.
Short answer
Big O describes how running time grows with input size. At a thousand items the gap is roughly 100 times; at a million items it is roughly 50,000 times, which is the difference between well under a second and many hours for the same machine.
Full expert answer
Computer science tutor
PhD candidate, Algorithms
The clearest way to justify the choice is to put numbers on the growth, then add the caveats that show you understand what Big O leaves out.
Put numbers on it
- n = 1,000: n log₂ n is about 10,000 operations, n² is 1,000,000
- n = 100,000: n log₂ n is about 1.7 million, n² is 10 billion
- n = 1,000,000: n log₂ n is about 20 million, n² is 1 trillion
If one basic operation takes a nanosecond, merge sort on a million items finishes in a fraction of a second. A quadratic sort on the same input needs around a trillion operations, which is closer to twenty minutes, and that is before real constant factors are counted.
Then add the caveats
- Big O hides constant factors, so a simple O(n²) algorithm can win on very small inputs, which is why many library sorts switch to insertion sort for short runs
- Merge sort needs O(n) extra memory, which matters on constrained systems
- Bubble sort is O(n) on already sorted data with an early-exit check, so input shape matters
This answer explains a method for you to apply to your own work. Copying it into a submission would count as plagiarism, and it is indexed by similarity checkers.
All questions