Written Exercises

Note: You should write this part in the written part of your solutions $($no need to submit code for this$).$

Exercise $1.$ Use Master Theorem to find the running time of a recursive algorithm in big$-$Oh notation if its running time is described by the following functions. If Master Theorem is not applicable, or if does not yield any result, mention that as well.

a$)T(n)=8T(\frac{n}{4})+n^2+logn$

$[1$ points$]$

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

$[1$ points$]$

c$)T(n)=121T(\frac{n}{11})+n^2$

$[1$ points$]$

d$)T(n)=8T(\frac{n}{2})+\frac{n^4}{logn}$

$[1$ points$]$

e$)T(n)=2T(\frac{n}{2})+n^3+n^2+n-1$

$[1$ points$]$

f$)T(n)=T(\frac{n}{3})+lo{g}^{2}n$

$[1$ points$]$

g$)T(n)=5T(\frac{n}{2})+n^4+logn$

$[1$ points$]$

h$)T(n)=8T(\frac{n}{4})+n^2+logn$

$3-1$

$3-2$

Assignment $3$: Queues, Recursion, and Hashing

$[1$ points$]$

i$)T(n)=27T(\frac{n}{3})+6n^3$

$[1$ points$]$

$)T(n)=nT(\frac{n}{4})+10n+1$

$[1$ points$]$