Frequently Arising Running Times

Common running time complexities

The table below shows an approximate running time of four algorithms on various input sizes for a hypothetical computer that performs $10^9$ operations per second. The last row shows the maximum value of $n$ for which the running time of the corresponding algorithm fits into one second.