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.
In more detail
If an algorithm really is O(f(n)), cost divided by f(n) stays bounded as n increases. If the ratio keeps climbing, the claim is too optimistic. The course uses this to confirm bounds with real counts instead of trusting a formula.
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.
- asymptotic analysis — Studying how an algorithm's cost behaves as the input size grows very large, ignoring constant factors and small inputs.
- benchmark — A repeatable measurement of how long code takes, or how much it uses, under a fixed workload, or more broadly a standard point of comparison such as an industry average.
Taught in
- Big O, Big Omega And Big Theta — Algorithms & Data Structures for Working Engineers