Description
1. Use the formal definition of Big-Oh to prove the extension of the Envelopment Property of Addition to more than two functions; that is, if
f1(n), f2(n), . . . , fx(n), and g1(n), . . . , gx(n) are functions of n such that
g1(n) = O(f1(n)), g2(n) = O(f2(n)), etc., then
Xx
i=1
gi(n) = O
Xx
i=1
fi(n)
!
,
for all x ≥ 2.
2. Use the properties of Big-Theta presented in class (not the formal definition) to prove that if f(n) = 561n lg(n)+17.9n
√
n+1024, g(n) = Θ(f(n)),
and h(n) = O(f(n)), then g(n)h(n) = O(n
3
). You may assume that ln n =
O(
√
n) and n
√
n = Ω(1). Hint: start by proving that f(n) = Θ(n
√
n).
1