Consider the algorithm below:

$1$: function Temp$($n : Z$+$ power of $2)$

$2$: if n $<=1$ then

$3$: return $1$

$4$: end if

$5$: temp $0$

$6$: for i from $1$ to n $1$ do

$7$: temp $$ temp $+1$

$8$: end for

$9$: return temp $+$ Temp$($n$/2)$

$10$: end function

$($a$)$ State the mathematical recurrence relation followed by Temp.

$($b$)$ Solve the recurrence relation to obtain the respective non$-$recursive expression.

$($c$)$ Give a tight O$()$ for the non$-$recursive expression. Don$$t forget the constants.

$3$