Solve the following recursions. Explain your answers. You can use any technique that we

have discussed in the lectures $($unrolling$,$ master theorem, $...).$

Note: You may assume that T $(1)=1,$ log refers to log base $2$ and n $=2$m

$1$

$1.$ T$($n$)=3$T$($n$/2)+$ n$2$

$2.$ T$($n$)=4$T$($n$/2)+$ n

$3.$ T$($n$)=$ T$($n $1)+$ n

$4.$ T$($n$)=2$T$($n$/2)+$ n log n

$5.$ T$($n$)=$

$$

$2$T$($n$/2)+$ log n

$$

$6.$ T$($n$)=3$T$($n$/3)+$ n

$7.$ T$($n$)=7$T$($n$/3)+$ n$2$

$8.$ T$($n$)=$ T$($

$$

n$)+$ log n