
15.1 Orders of Magnitude and Big-Oh Notation 1121
rithms that compute a factorial as a function of their input, then we can
compare the relative efficiency of each algorithm. In other cases, such as
sorting an array of integers, the running time depends on the number of
array elements. Similarly, if we express the running time as a function of
the number of elements in the array, we can compare the relative efficiency
of multiple sorting algorithms.
The input value or number of inputs for an algorithm represent the size of
the problem for which we are trying to compute the running time. We will
call that number n. We are interested in relative time, ...