Java Reference
In-Depth Information
n n = 1
n(n
n1
) n > 1
n
n
=
At this point, our intuition should be telling us pretty clearly the relative
growth rates of these three functions. But how do we prove formally which
grows the fastest? And how do we decide if the differences are significant
in an asymptotic sense, or just constant factor differences?
We can use logarithms to help us get an idea about the relative growth
rates of these functions. Clearly, log 2
n
= n. Equally clearly, log n
n
=
n log n. We can easily see from this that 2
n
is o(n
n
), that is, n
n
grows
asymptotically faster than 2
n
.
How does n! fit into this? We can again take advantage of logarithms.
Obviously n! n
n
, so we know that log n! is O(n log n). But what about
a lower bound for the factorial function? Consider the following.
= n (n 1)
n
2
(
n
n!
2
1) 2 1
n
2
n
2
n
2
1 1 1
(
n
2
)
n=2
=
Therefore
log n! log(
n
2
)
n=2
= (
n
2
) log(
n
2
):
In other words, log n! is in (n log n). Thus, log n! = (n log n).
Note that this does not mean that n! = (n
n
). Because log n
2
=
2 log n, it follows that log n = (log n
2
) but n 6= (n
2
). The log func-
tion often works as a “flattener” when dealing with asymptotics. That is,
whenever log f(n) is in O(log g(n)) we know that f(n) is in O(g(n)).
But knowing that log f(n) = (log g(n)) does not necessarily mean that
f(n) = (g(n)).
Example14.7
What is the growth rate of the Fibonacci sequence? We
define the Fibonacci sequence as f(n) = f(n 1) + f(n 2) for n 2;
f(0) = f(1) = 1.
In this case it is useful to compare the ratio of f(n) to f(n 1). The
following table shows the first few values.
n
1
2
3
4
5
6
7
f(n)
1
2
3
5
8
13
21
f(n)=f(n 1)
1
2
1:5
1:666
1:625
1:615
1:619
