Algo HW #1

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)\)