Asymptotic notation estimates how an algorithm grows as the problem size becomes large. Big-O keeps the fastest-growing part while ignoring lower-order terms and constant factors. section 3.4.2
Common estimates include:
- A direct solver for N equations may require up to N! steps, giving O(N!). section 3.4.2
- Summing every matrix element requires N² work, written O(N²). section 3.4.2
- Adding N extra operations changes N² to N² + N, but the estimate remains O(N²). section 3.4.2
- A computation modeled by 2N³ − N² becomes O(N³), because the cubic term dominates. section 3.4.2
Comparing algorithms
When implementation speed depends on caches, latencies, or the particular problem instance, asymptotic notation supplies a theoretical estimate based only on input size. section 3.4.2
