$3)$ Let T $($n$)$ be the number of multiplication that the function fct does.

int fct$($int n$)$

$\{$

if $($ n $==0)\{$

return $1$;

$\}$

int sum $=1$;

for$($int i $=0$; i $<$ n; i$++)\{$

sum $=$ sum $*$ n;

$\}$

return fct$($n$-1)$;

$\}$

Write a recurrence relation for T$($n$)$

Solve the recurrence relation to obtain T$($n$)$ in terms of n$.$ Show your workings.

$4)$ Let T $($n$)$ be the number of addition that the function fct does.

int fct$($int n$)$

$\{$

if $($ n $==1)\{$

return $1$;

$\}$

return fct$($n$/2)+1$;

$\}$

Write a recurrence relation for T$($n$)$

Solve the recurrence relation to obtain T$($n$)$ in terms of n$.$ Show your workings.