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

Taught in

References