Page 235 - Discrete Mathematics and Its Applications

214 3 / Algorithms

2
EXAMPLE 8 Give a big-O estimate for f (n) = 3n log(n!) + (n + 3) log n, where n is a positive integer.

Solution: First, the product 3n log(n!) will be estimated. From Example 6 we know that log(n!)
is O(n log n). Using this estimate and the fact that 3n is O(n), Theorem 3 gives the estimate
2
that 3n log(n!) is O(n log n).
2
2
2
Next, the product (n + 3) log n will be estimated. Because (n + 3)< 2n when n> 2, it
2
2
2
2
follows that n + 3is O(n ). Thus, from Theorem 3 it follows that (n + 3) log n is O(n log n).
Using Theorem 2 to combine the two big-O estimates for the products shows that f (n) =
2
2
3n log(n!) + (n + 3) log n is O(n log n). ▲
2
2
EXAMPLE 9 Give a big-O estimate for f(x) = (x + 1) log(x + 1) + 3x .
2
Solution: First, a big-O estimate for (x + 1) log(x + 1) will be found. Note that (x + 1) is
2
2
O(x). Furthermore, x + 1 ≤ 2x when x> 1. Hence,
2
2
2
log(x + 1) ≤ log(2x ) = log 2 + log x = log 2 + 2 log x ≤ 3 log x,
2
if x> 2. This shows that log(x + 1) is O(log x).
2
2
2
From Theorem 3 it follows that (x + 1) log(x + 1) is O(x log x). Because 3x is O(x ),
2
2
Theorem 2 tells us that f(x) is O(max(x log x, x )). Because x log x ≤ x , for x> 1, it follows
2
that f(x) is O(x ). ▲
Big-Omega and Big-Theta Notation
Big-O notation is used extensively to describe the growth of functions, but it has limitations. In
particular, when f(x) is O(g(x)), we have an upper bound, in terms of g(x), for the size of f(x)
for large values ofx. However, big-O notation does not provide a lower bound for the size off(x)
for large x. For this, we use big-Omega (big- ) notation. When we want to give both an upper
and are the Greek
and a lower bound on the size of a function f(x), relative to a reference function g(x), we use big-
uppercase letters omega
and theta, respectively. Theta (big- ) notation. Both big-Omega and big-Theta notation were introduced by Donald
Knuth in the 1970s. His motivation for introducing these notations was the common misuse of
big-O notation when both an upper and a lower bound on the size of a function are needed.
We now define big-Omega notation and illustrate its use. After doing so, we will do the
same for big-Theta notation.
DEFINITION 2 Let f and g be functions from the set of integers or the set of real numbers to the set of real
numbers. We say that f(x) is (g(x)) if there are positive constants C and k such that

|f(x)|≥ C|g(x)|

whenever x> k. [This is read as “f(x) is big-Omega of g(x).”]

There is a strong connection between big-O and big-Omega notation. In particular, f(x) is
(g(x)) if and only if g(x) is O(f (x)). We leave the verification of this fact as a straightforward
exercise for the reader.
2
3
3
EXAMPLE 10 The function f(x) = 8x + 5x + 7is (g(x)), where g(x) is the function g(x) = x . This
3
2
3
is easy to see because f(x) = 8x + 5x + 7 ≥ 8x for all positive real numbers x. This is
2
3
3
equivalent to saying that g(x) = x is O(8x + 5x + 7), which can be established directly by
turning the inequality around. ▲