Homework 5

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

## Reviews

There are no reviews yet.