RSA Laboratories

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

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.


  • With f(n) = 1/n, we have

    n ® ¥
    f(n) = 0.

  • One may prove that
    n ® ¥ 
    na bn = 0

    whenever b > 1.

  • With f(n) = en + n2, we have
    n ® ¥ 
    f(n) = ¥,

    that is, f(n) tends to infinity when n grows large. However,

    n ® ¥
    f(n) en < = 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 ``big-O'' 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)| £ C|g(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 en is O(en), because

|f(n)| £ 7 en.

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(nk). We say that an algorithm is sub-exponential if f(n) is O(an) for all a > 1. All polynomial time algorithms are sub-exponential, but there are sub-exponential time algorithms that are not polynomial. For example, with f(n) = eÖn we have

f(n)/an = eÖn- n loga ® 0


f(n)/nk = eÖn- k logn ® ¥

when n tends to infinity. The algorithm is an exponential time algorithm if it is not sub-exponential and if it is O(bn) for some b > 1. There are algorithms that are even slower than exponential (for example, consider f(n) = exp(n2). However, in most applications the ``worst'' algorithms are at most exponential.

Top of the page