We typically plot , but it's sometimes useful to plot

in order to experimentally determine the asymptotic running time of an algorithm.

The idea is to run the algorithm with many different input sizes, . For each run, the point is plotted on a log/log graph. A line is drawn through the points. We'll see later how the slope and intercept of the line tell us the asymptotic running time.

In the log/log graph below, the running times are shown as red points and the blue line is is drawn through them. The points corresponding to larger are given more importance when choosing the line, since it's with larger that the dominant term of the running time is more evident.

The intercept is and the slope is . We'll use these later.

We will assume that the dominant term of the running time is of the form

(We will ignore lesser terms in the running time because the dominant term is the only one that affects the asymptotic behaviour of the algorithm.)

Finding c

Finding k

To experimentally determine the running time, plot on a log/log graph. Draw a line through the points, giving greater weight to those corresponding to larger . Let be the line's intercept and be the line's slope. Then, as gets large, is closely approximated by

and you've determined that the running time of the algorithm is (at least empirically) in .

Example