Big-O describes the behavior as the data approaches infinity. The problem is that your actual data is rarely anywhere near infinity.
What does Big-O leave out?
This notation intentionally omits constants and lower-order terms. An algorithm 100n and an algorithm n are both O(n), even though the first one is a hundred times slower for all data sizes.
A classic example: sorting a small array
Insertion sort is O(n²), while merge sort is O(n log n). Yet all standard libraries switch to insertion sort when the array has fewer than a few dozen elements. The reason:
- The sequential insertion and access order allows the CPU cache to predict the sequence, so it almost never misses
- It does not require secondary memory allocation
- The inner loop is extremely simple, with few branch instructions
For n = 20, the small constant clearly outperforms the growth rate.
Memory is now more expensive than computation
An addition operation takes less than one nanosecond. A cache miss that requires a read from RAM takes about one hundred nanoseconds. That means a single cache miss is equivalent to a hundred calculations.
Therefore, traversing a contiguous array is usually faster than traversing a linked list, even though both are O(n). An array is stored contiguously in memory, so the CPU preloads the next element; in a linked list, however, each node is stored in a separate location.
How to Use Big-O Correctly
- Use it to weed out bad designs right from the start—O(n²) on a million elements is indisputable
- Don’t use it to choose between two options of the same order of magnitude — measure instead
- Always ask how large the actual data set is, because the answer is usually smaller than you think
Thảo luận