A.7 Time estimations and some complexity theory
Let N be the set of nonnegative integers and let R be the set of real numbers. In the study of functions f : N ® R one often wants to estimate the approximate size of f(n) for large n. The concept of limits is very helpful for such instances. If f(n) approaches a real number c as n becomes larger, then f(n) is said to have the limit c as n tends to infinity, denoted
lim n ® ¥ 
f(n) = c. 
Formally, f(n) has the limit c if for each e > 0 there is a number N such that f(n)c £ e for all n ³ N.
Examples.

With f(n) = 1/n, we have
lim
n ® ¥f(n) = 0.
 One may prove that
lim
n ® ¥n^{a} b^{n} = 0 whenever b > 1.

With f(n) = e^{n} + n^{2}, we have
lim
n ® ¥f(n) = ¥,
that is, f(n) tends to infinity when n grows large. However,
lim
n ® ¥
f(n) e^{n} < = 1 by the previous example.
In the last example, the second limit told us more about the function f than the first. The procedure of estimating a complicated function f using an easier function g such as a polynomial or an exponential function is sometimes very useful. However, instead of trying to compute the exact limit of the fraction f(n)/g(n) as in the example, one might be content with only a rough estimate of the behavior of the fraction. The ``bigO'' notation has proven to be a very useful tool for this purpose. Formally, we say that f(n) is O(g(n)) if there is a constant C such that f(n) £ Cg(n) for all n (or at least for all n larger than some integer N). This means that the fraction f(n)/g(n) is bounded by the constant C. For example, f(n) = 7 sin n e^{n} is O(e^{n}), because
f(n) £ 7 e^{n}. 
Say that we have an algorithm (a procedure taking an input and producing an output following certain rules) and let f(n) denote the maximal time needed to produce the output, where n is the size of the input. For instance, if the input is an integer, then n is normally the number of digits in the binary representation of the integer.
We say that the algorithm is a polynomial time algorithm in n if there is an integer k such that f(n) is O(n^{k}). We say that an algorithm is subexponential if f(n) is O(a^{n}) for all a > 1. All polynomial time algorithms are subexponential, but there are subexponential time algorithms that are not polynomial. For example, with f(n) = e^{Ön} we have
f(n)/a^{n} = e^{Ön n loga} ® 0 
and
f(n)/n^{k} = e^{Ön k logn} ® ¥ 
when n tends to infinity. The algorithm is an exponential time algorithm if it is not subexponential and if it is O(b^{n}) for some b > 1. There are algorithms that are even slower than exponential (for example, consider f(n) = exp(n^{2}). However, in most applications the ``worst'' algorithms are at most exponential.