Pitfalls and Real-World Performance

What Big-O leaves out

Common analysis mistakes: forgetting the cost of library calls (in on lists, slicing, string concatenation); ignoring recursion stack space; confusing best case with typical behaviour; writing O(n²) when two different inputs call for O(n · m); claiming a nested loop is quadratic when amortised reasoning shows it is linear; and forgetting the log factor of sorting. Big-O also hides things that matter in practice. Constant factors: an O(n) algorithm that does 50 operations per element can lose to an O(n log n) one doing 2 per element for realistic n. Memory hierarchy: contiguous arrays are often much faster than linked structures with the same complexity, because of CPU caches. Small inputs: for n below a few dozen, simple O(n²) algorithms can beat sophisticated ones, which is why libraries switch to insertion sort for small slices. I/O and network: one database round trip can cost more than millions of CPU operations. Use complexity to choose sensible approaches, then measure with profilers and benchmarks to confirm.

Same complexity, different speed

Both functions are O(n), but memory layout and constants differ.

import array

# summing 10 million numbers: both O(n)
nums_list = list(range(10_000_000))
nums_packed = array.array("q", range(10_000_000))

total_a = sum(nums_list)          # list of pointers to integer objects
total_b = sum(nums_packed)        # compact array of machine integers

# with NumPy, a vectorised sum runs in optimised C over contiguous memory:
# import numpy as np; total_c = np.arange(10_000_000).sum()
# expect large constant-factor differences even though all are O(n);
# measure with timeit on your machine rather than assuming

Optimise the right thing

Profile before optimising. A function with excellent complexity can still be the bottleneck because it makes a network call per item; reducing round trips often matters more than shaving a log factor.

त्वरित जाँच: Why might an O(n log n) algorithm beat an O(n) algorithm in practice for realistic input sizes?

• Constant factors, memory access patterns and implementation details can outweigh the asymptotic difference
• Big-O is always wrong
• O(n log n) is always faster
• log n is negative for large n