(1)

For each of the following pairs of functions f(n) and g(n), give an appropriate positive constant c such that for all n>1.

1.

2.

3.

(2)

Prove that if and , then.

(3)

List the functions below from the lowest to the highest order. If any two or more are of the same order, indicate which.

(4)

For each of the following pairs of functions, either f(n) is in O(g(n)), f(n) is in (g(n)), or f(n)=(g(n)). Determine which relationship is correct and briefly explain why.

1.

2.

3.

Problem 1 (6 points) For each of the following pairs of functions fin) and g(n), give an appropriate positive constant c such that f(n) Sc.g(n) for all n>1. 1. f(n) = n2 +n + 1, g(n) = 2n3 2. f(n)= nn+n?, g(n) = n2 3. f(n) = n2 -1 +1, g(n) = n2/2 Problem 2 (3 points) Prove that if f1(n) = N(91(n)) and f2(n) = N(92(n)), then f1(n) + f(n) = N(91(n) + g2 (n)) Problem 3 (3 points) List the functions below from the lowest to the highest order. If any two or more are of the same order, indicate which n m2 nlog (n) n-n+ 75 m2 + log (n) vn 21-1 log log(n) n! (log(n)) e" ni+ where 0