Consider the following algorithm:

int f$($n$)$

$/*$ n is a positive integer and n is a power of two $*/$

if $($n return n

int x $=$ f$($n$/2)$

for int i$=1$ to n$/2$ do

x $=$ x $+($i $*$ i$)$

$/*$ loop ends here $*/$

int y $=$ x $+$ f$($n$/2)$

int z $=$ y $+$ f$($n$/2)$

return z

Let T$($n$)$ be the time f$($n$)$ takes. Write a recurrence formula for T$($n$)($you do not need to solve the recurrence$).$

Consider the following algorithm:

int $f(n)$

$\frac{?}{{?}^{***}n}$ is a positive integer and $n$ is a power of two $*/$

if $(n1)$ return $n$

int $x=f(\frac{n}{2})$

for int $i=1$ to $\frac{n}{2}$ do

$x=x+(i^{***}i)$

$\frac{?}{?}**$ loop ends here $*/$

int $y=x+f(\frac{n}{2})$

int $z=y+f(\frac{n}{2})$

return $z$

Let $T(n)$ be the time $f(n)$ takes. Write a recurrence formula for $T(n)($you do not

need to solve the recurrence$).$