Homework 4 Formal definition of Big-Oh

Homework 4

1. Use the formal definition of Big-Oh to prove that if f(n) = O(g(n)), then
f(n) + g(n) = O(g(n)).
2. Prove that if f(n) is a polynomial of the form X
d
i=1
ain
xi
, for some coefficients a1, a2, . . . , ad and exponents x1, x2, . . . , xd, then f(n) = Θ(n
max{x1,x2,...,xd}
).
Hint: you may use any property of Big-Oh notation listed in the slides.
You may wish to use induction for this problem.
3. (Bonus) Prove that 2n = Ω(n
k
) for all integers k ≥ 1.
1