CS $33200$ Algorithms

Homework $2$

$1[30$ points$]$ Arrange the following list of functions in ascending order of growth rate. That is$,$

if function $g(n)$ immediately follows function $f(n)$ in your list, then $f(n)$ should be $O(g(n))$ :

$(n-2)!in((n-2)!),5lg(n+100{)}^{10}=50lg(n+100)in(logn),2^{2n}=$

$(2^2{)}^{n}in(4^n),0\mathrm{.}001n^4+3n^3+1in(n^4),l{n}^2$nin$(lo{g}^{2}n),\sqrt[3]{n}in$

$(n^{\frac{1}{3}}),3^{n}in(3^n)$

$2[30$ points$]$

Use the master method to give tight asymptotic bounds for the following recur$-$

rences.

a$.T(n)=2T(\frac{n}{4})+1.$

b$.T(n)=2T(\frac{n}{4})+\sqrt[\phantom{2}]{n}.$

$3[40$ points$]$

a$.[20$ points$]$ Draw the recursion tree for $T(n)=4T(\frac{n}{2})+n$ and provide an upper

asymptotic bound on its solution.

b$.[20$ points$]$ Solve the recurrence with a method of your choice.

$T(n)=2T(\frac{n}{2})+1$