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

Taught in

References