GROWTH OF FUNCTIONS


We want to make more precise the notion that one function is
insignificant with respect to another in the long run; that two
functions are similar in the long run; etc.

We will consider two functions as being in the same family if one is a
positive constant multiple of the other.  Thus x^2 and 3.2 x^2 are in the
same family.

Now let f and g be functions; we in particular are concerned with the
case where f and g are defined on positive integers, and we then write
f(n) and g(n).  We also are usually interested only in cases where the
values of f and of g are positive.

We consider f to be dominated by g's family if one of the family
members, say cg, can eventually keep up with f: there exists an n_0
and a c>0 such that f(n) <= g(n) for all n > n_0.  In effect, g tells
f "I have a big sister who's at least as big as you, at least after a
certain age".  That is, f(n) is less than or equal to some constant
multiple of g(n), from some point on.

The technical version is this:

f = O(g) ["f is big-O of g'] means that there exists an n_0 and a c > 0
such that for all n > n_0, f(n) <= cg(n).


EXAMPLE 1:  x = O(x^2)

Here x^2 does not need to invoke help froma big sister, since x^2 is
already bigger than x, at least for x>1.  We just need t ofind
constants c and n_0 to make this precise.  But we let c=1 since we
suspect x^2 itself will be big enough; and we let n_0 = 1 since
then if x>n_0 we'll have x>1; and then x^2 > x (by multiplying both
sides by x).


EXAMPLE 2:  x^2 + 1 = O(x^2).

Note that although x^2 + 1 is always greater than x^2, if we consider
a suitable multiple of x^2, say for instance 3x^2, then this family
member of x^2 outgrows x^2 + 1 for large x.  Specifically:

     x^2 + 1 <= 3(x^2)  iff  1 <= 2x^2  iff  x^2 >= 1/2

iff

     x >= 1/sqrt(2)

But sqrt(2) > 1, so 1/sqrt(2) < 1, o for all x > n_0 we have x > 1/sqrt(2). 

Then we choose n_0 = 1, and c = 3, and it follows that x^2 + 1 =
O(x^2).


EXAMPLE 3: x^2 = O(x^2 - x).

We want x^2 <= c[x^2 - x], so we hunt for c:

   x^2 <= c[x^2 - x]  iff  1 <= c[1 - 1/x]

iff

   c >= 1/[1 - 1/x] = 1/[(x-1)/x] = x/(x-1)

How can we guarantee that c >= x/(x-1)?  well, x/(x-1) is always > 1,
but also is <= 2 for large x.  In fact, lim x/(x-1) = 1 at infinity.
At what point does x/(x-1) become, and stay, less than 2?  From
calculus we find its derivative is -1/(x-1)^2 which is negative (for
x > 1). Thus x/(x-1) is decreasing (for x > 1).  And at x=2, for
example, x/(x-1) = 2, so it is less than 2 for x > 2.  So let c = 2
and then we will have  c >= x/(x-1) for x > 2.  Thus n_0 can also be
taken to be 2.


EXAMPLE 4: x^3 =/= O(x^2)

This example shows that not all functions are big-Oh of one another!
We need to show that there is no big sister c x^2 that is bigger than
x^3 from some point on.  So, let c x^2 be any member of the family of
x^3, and let n_0 be any positive real number.  We'll find an x > n_0
such that x^3 > c x^2.  We'll start with that last inequality and work
backwards to see what x will work.  We have

    x^3 > c x^2
iff
    1  > c/x  (note that x > 0 since x > n_0)
iff
    x > c

So all we have to do is choose x > c, and we are guaranteed that the
family member c x^2 will not dominate x^3.  But c x^2 was any family
member at all; so x^2 has no family member that can keep up with x^3,
and so x^3 is not big-Oh of x^2.

But it's worse than that (from x^2's point of view): not only does it
*not* have a family member that can keep up with x^3 -- and thus x^3
is not O(x^2) -- but x^3 can keep up x^2 So, first of all, x^2 =
O(x^3) -- since we can let c = 1 and x > n_0 = 1 to guarantee that x^2
< c x^3 = x^3 .  But x^3 is even faster-growing than that: it not only
keeps up with x^2 but also with its whole family!  There is a special
notation fof this: x^2 = o(x^3), or "x^2 is little-oh of x^3".

Definition:  f = o(g) means that for every c>0 there is an n_0 such
that for all x > n_0, f(x) < c g(x).

That is, every member of g's family beats f, even when c < 1.  Note
that this is the same as saying that g beats every member of f's
family, since we can just divide by c to get 1/c f(x) < g(x), where
1/c f(x) is simply any member of f's family.

So f = o(g) is a very strong statement, stronger than f = O(g). The
latter says some multiple g can keep up with f; the former says every
multiple of g can do so, even tiny multiples. To do that, g must
indeed grow very fast compared to f, such as x^3 does compared to x^2.


Big-Oh and little-oh are the essential notions of growth of functions,
but there are a few others notations that are sometimes useful, which
ae easily define in terms of these two:

f = Theta(g) means f = O(g) and also g = O(f)

f = Omega(g) means g = O(f)

f = omega(g) means g = o(f)


EXAMPLES

x^2 = Theta(x^2 - x)

x = o(x^2)

x^2 = omega(x)


Theta can also be defined as follows:

f = Theta(g) iff there are constants c_1>0, c_2>0, and n_0, such that
for all n > n_0,  c_1 g(n) <= f(n) <= c_2 g(n) .  Note that c_1 and
c_2 give the two Big-Oh halves of our original definition of Theta.


Now for a more practical example: runtime of insertion sort.  Recall that

 T_INSRT (n) <= 0.5 n^2 - 0.5 n (upper bound, worst case)

and 

 n-1 <= T_INSRT (n) (lower bound, best case)

So, 

 T_INSRT (n) = O(n^2) 

and also 

 n = O(T_INSRT (n))

The latter can be more nicely expressed as T_INSRT (n) = Omega(n).


Now let's give an overview of common functions and how they "line up"
in terms of growth.  The following list is in order of slowest-growing
to largest, where f = o(g) for each side-by-side pair f,g:

   1/n   1   lg n   n   n*lg n   n^2   ...   n^k   ...   2^n   n!   n^n

In many cases, one can prove the little-oh relation by the following
means:  show lim f/g = 0 at infinity.  The reason this can be used is
that since we want to show f < cg for all c, this means we'll be
showing f/g < c, for all c, ie f/g is smaller than any positive c,
eventually (ie for x > some n_0).  But this is just the definition of
a limit = 0 at infinity.

EXAMPLE:  lg n = o(n).  For consider lim (lg n)/n at infinity. By
L'Hopital's Rule, this is lim (1/n)/1 = lim 1/n = 0.

This also works the other way around: if the lim is not 0, then
little-oh fails; for instance, lim (n - lg n)/n = lim [1 - (lg n)/n]
= 1, so n - lg n is *not* o(n).

EXAMPLE: lg(lg n) = o (lg n).  Here lim lg(lg n) / lg n = 
lim 1/(lg n) 1/n / 1/n = lim 1/(lg n) = 0 since lim lg n = infinity.

In cases involving n!, there is a useful formula -- Stirling's formula:  

 n! = sqrt(2 pi n) (n/e)^n (1 + Theta(1/n))

What this means is that, for large n, we have the approximation

 n! ~ sqrt(2 pi n) (n/e)^n (1 + f(n))

where f(n) = Theta(n), ie, f(n) is a function that, for large n,
behaves like 1/n, and hence tends to zero.


One can also sometimes use limits to show a Theta relation, but one
must be careful since it does not always apply.

EXAMPLE:  2n^2 = Theta(n^2 -n).  Note that lim [2n^2 / (n^2 - n)] at
infinity is also 1 / lim [(n^2 - n) / 2n^2] which in turn is
1 / lim [1/2 - 1/2n] = 1 / (1/2) = 2.  So the two functions, 2n^2 and
n^2 - n, stay within a factor of about 2 of each other, for large n.
In particular, for large n, each is less than 3 times the other, and
this shows each is Big-Oh of the other, hence the Theta relation
holds.

In general whenever a finite limit of the ratio of two functions
exists at infinity, they are Theta of each other; but the converse
need not hold.

Web Accessibility