asymptotic analysis
Studying how an algorithm's cost behaves as the input size grows very large, ignoring constant factors and small inputs.
In more detail
Asymptotic statements such as "merge sort is O(n log n)" describe the trend, not the exact number of steps. Constants and small values of n are dropped because, as n grows, the fastest-growing term dominates everything else. The course checks such claims empirically by dividing measured cost by the claimed function and watching whether the ratio stays bounded.
Related terms
- Big O notation — A way of writing an upper bound on growth: O(f(n)) means the cost grows no faster than a constant times f(n) for large n.
- big Omega notation — A way of writing a lower bound: Omega(f(n)) means the cost grows at least as fast as a constant times f(n) for large n.
- big Theta notation — A way of writing an exact growth rate: Theta(f(n)) means the cost is both O(f(n)) and Omega(f(n)).
- ratio test — An experimental check of a growth claim: divide the measured cost by the claimed function, such as n log n, and see whether the result stays roughly constant as n grows.
Taught in
- Why Complexity Matters In Production — Algorithms & Data Structures for Working Engineers
- Big O, Big Omega And Big Theta — Algorithms & Data Structures for Working Engineers
- Heaps And Priority Queues — Algorithms & Data Structures for Working Engineers
- Dynamic Programming: Memoisation And Tabulation — Algorithms & Data Structures for Working Engineers