# Problem 1

1. $$f(n)=\sqrt{2^{7n}}, g(n)=lg(7^{2n})$$

$$f(n)=2^{7n/2}, g(n)=2nlg(7)$$

$$f(n)=lg(2^{7n/2}), g(n)=lg(2nlg(7))$$

$$f(n)=lg(2^{7n/2}), g(n)=lg(2nlg(7))$$

$$f(n)=7n/2, g(n)=lg(2n) + lg(lg(7))$$

$$f(n)=7n/2, g(n)=lg(2n)$$

$$f=\Omega(g)$$

2. $$f(n)=2^{nln(n)}, g(n)=n!$$

$$f(n)=ln(2^{nln(n)}), g(n) = ln(n!)$$

$$f(n)=nln(n), g(n) = nlg(n)$$ (via previously proved identity)

$$f=\theta(g)$$

3. $$f(n)=lg(lg^*n), g(n)=lg^*(lgn)$$

$$f=O(g)$$

4. $$f(n)=\frac{lgn^2}{n},g(n)=lg^*n$$

$$f=O(g)$$ via limits. f approaches 0.

5. $$f(n)=2^n, g(n)=n^{lgn}$$

$$f(n)=n, g(n)=(lgn)^2$$

$$f=\Omega(g)$$

6. $$f(n)=2^{\sqrt{lgn}}, g(n)=n(lgn)^3$$

$$f(n)=(lgn)^{1/2} , g(n)=lg(n)+lg((lg(n))^3)$$

$$f=O(g)$$

7. $$f(n)=e^{cos(n)}, g(n)=lgn$$

$$f(n)=cos(n), g(n) = ln(lg(n))$$

$$f= O(g)$$

8. $$f(n)=lgn^2,g(n)=(lgn)^2$$

$$f(n)=2lg(n), g(n)=(lgn)^2$$

$$f=O(g)$$

9. $$f(n)=\sqrt{4n^2-12n+9}, g(n)=n^(\frac{3}{2})$$

$$f(n)=2n, g(n)=n^(\frac{3}{2})$$

$$f(n) = O(g)$$

10. $$f(n)=\sum_{k=1}^{n} k, g(n)=(n+2)^2$$

$$f(n) = \frac{k(k+1)}{2}$$ via summation formula $$g(n)=(n+2)^2$$

$$f=\theta(g)$$