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$)=8$T$($n$/4)+$ n

$2+$ log n

$[1$ points$]$

b$)$ T$($n$)=2$T$($n$/8)+$

n

$[1$ points$]$

c$)$ T$($n$)=121$T$($n$/11)+$ n

$2$

$[1$ points$]$

d$)$ T$($n$)=8$T$($n$/2)+$ n

$4$

log n

$[1$ points$]$

e$)$ T$($n$)=2$T$($n$/2)+$ n

$3+$ n

$2+$ n $1$

$[1$ points$]$

f$)$ T$($n$)=$ T$($n$/3)+$ log$2$

n

$[1$ points$]$

g$)$ T$($n$)=5$T$($n$/2)+$ n

$4+$ log n

$[1$ points$]$

h$)$ T$($n$)=8$T$($n$/4)+$ n

$2+$ log n

$3-1$

$3-2$ Assignment $3$: Queues, Recursion, and Hashing

$[1$ points$]$

i$)$ T$($n$)=27$T$($n$/3)+6$n

$3$

$[1$ points$]$

j$)$ T$($n$)=$ nT$($n$/4)+10$n $+1$