GROWTH OF FUNCTIONS


We want to make more precise the notion that one function is
insignificant with respect to another in the long run; or 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 g's family
members, say cg, can eventually keep up with f: there exists an n_0
and a c>0 such that f(n) <= cg(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-Oh of g''] means that there exists an n_0 >=1 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 from a big sister, since x^2 is
already bigger than x, at least for x>1.  We just need to find
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, so for all x >= 1 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).  Note: we could also have used c=2, or indeed *any* c > 1, but
then we might need to use a different n_0.


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 at least a big as
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 whole 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 >= 1)
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 for 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 >= 1 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>=1, 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 fastest, 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 3^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>0, 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))

where Theta(1/n) is being used to represent some function that
``grows'' like 1/n, eg that shrinks to 0 as n --> oo.

For large n, this gives us the approximation

 n! ~ sqrt(2 pi n) (n/e)^n

[The meaning of ~ is this: for functions f and g with f >= g, f ~ g
means f = g + o(g).  More generally, f ~ g means |f - g| = o(g). That
is, f and g are very close to each other, so close that their
difference is very small compared to the size of either of them.]

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 non-zero limit of the ratio of two functions
exists at infinity, they are Theta of each other; but the converse
need not hold.

Below are some further examples.

big-Oh and Theta problems

There is no one perfect method for all big-Oh or Theta problems. Usually by looking at the problem, you can figure out a good method for that case. In general, you need to think about which mathematical manipulations will give you whatever you need to get the big-Oh inequality.

Here is an example of a big-Oh problem, along with several different methods of solution: Show that $n^2+5n+10=O(n^2)$. We need to show that there exist constants $c > 0$ and $n_0 \geq 1$ such that LHS $\leq cn^2$ for all $n \geq n_0$. We will give four solutions:

Solution A: Note that if $5n$ and $10$ on the LHS were each replaced by $n^2$, we'd have simply $3n^2$, and then we could choose $c=3$ in order to get LHS $\leq cn^2$. We cannot of course simply change things. But we can say that LHS $\leq n^2+n^2+n^2$ if $n \geq 5$ since for $n \geq 5$ we do have $5n \leq n^2$ and $10 \leq n^2$. So let $n_0=5$ and $c=3$; then LHS $\leq cn^2$ for $n \geq n_0$, so we are done.

Solution B: Divide both sides by $n^2$; so we need to show

$$1 + 5/n + 10/n^2 \leq c$$

But if $n \geq 5$ then this new LHS $\leq 1+1+1$ since for $n \geq 5$ we have $5/n \leq 1$ and $10/n^2 \leq 1$. So let $n_0=5$; then we have the new LHS $\leq 3$ so pick $c=3$.

Solution C: The (original) LHS is too big compared to the RHS, to use $c=1$. But the $n^2$ on the RHS grows faster than the terms $5n$ and $10$ on the LHS, so if we multiply the RHS by $2$ to get $2n^2$ then one of the $n^2$s matches that on the LHS, and the other will outstrip $5n + 10$ for large enough $n$. So let $c=2$ and we hunt for a large enough $n_0$ to make

$$n^2 + 5n + 10 \leq 2n^2$$

which will hold iff

$$n^2 -5n -10 \geq 0$$

But this is true if $n \geq 7$ since (i) $7^2 -5 \cdot 7 -10 > 0$ and (ii) the deriv is positive for $n \geq 7$ as well. So let $n_0 = 7$.

Solution D: As in solution C, try $c=2$ (for the same reason); but then solve $n^2 -5n -10 = 0$ to get one negative root and also $n=(5 + \sqrt{65})/2$ which is less than $7$. So the only roots of $n^2 -5n -10$ are less than $7$, and at $n=7$ this polynomial is positive, hence it must stay positive for all $n \geq 7$ (else it would have to cross the x-axis somewhere and have another root).

Now for a THETA problem, you have to do two big-Oh problems, one in each direction. One direction gives you values for $c$ and $n_0$, and so does the other, but they might not be the same values. But you can take the larger of the two n's and call that simply $n_0$. This is because if one $n_0$ works, so does any larger value. The c's however cannot be combined into one, since they occur in different inequalities.

Example of Stirling's formula and similarity of functions

To show that $n! \sim \sqrt{2 \pi n} (n/e)^n$, use Stirling's formula: $n! = \sqrt{2 \pi n} (n/e)^n (1 + \Theta(1/n))$. That is, substitute the RHS of Stirling into the LHS of what you are to show, and try to show the result holds, using the fact that $f(n) \sim g(n) \iff f(n) = g(n) + o(g(n))$. I.e., replace $\sim$ by the equation with little-oh, and prove the result.

To simplify the writing, let $G(n)$ be the missing function $\Theta(1/n)$; that is, write G(n) in place of $\Theta(1/n)$, where $G(n)$ is some function such that $G(n) = \Theta(1/n)$. You will find that most things cancel out of the formula, and all you have to do is prove the bit that is left. It will have little-oh in it, so use the limit version to do this last part.