It is the most fundamental method for analyzing and comparing the behavior of programs. Recall that a function F may require on the order of N steps and a function G steps, even though both compute the same results for the same inputs. Now suppose the basic time constants are 1000 for F and 1 for G . But a closer look reveals that as the inputs get larger, G 's advantage decreases. Indeed, for an input of size 1000, the two functions need the same number of steps, and thereafter G is always slower than F .
Figure compares the graphs of the two expressions.
It shows that the linear graph for dominates the curve of for some finite number of points but thereafter it is below the curve. The concrete example recalls two important facts about our informal discussion of abstract running time. The comparison of functions on N is difficult because they are infinite. If a function f produces larger outputs than some other function g for all natural numbers, then f is clearly larger than g . Because we would still like to make approximate judgements, programmers and scientists adapt the mathematical notion of comparing functions up to some factor and some finite number of exceptions.