Asymptotic Complexity

Given two functions

f,g : R+ 7R, 1. f O(g(n)) if and only if c R+,n0 R0(n n0 (f(n) cg(n))).

2. f (g(n)) if and only if c R+,n0 R0(n n0 (f(n) cg(n))).

3. f (g(n)) if and only if O(g(n)) and (g(n)).

1. Give derivations that prove the following. For convenience, you may assume that the logarithms are in the base of your choice, but you should specify what base you are using in your derivation.

(a) (n8)2 (n2).

(b) 7n4 5n3 logn6n2 + 9nlogn13n (n4).

(c) 2log(3n3 n2 + 43) O(logn).