$(15$ pts$)($Running time complexity$)$ Find the running time complexity of the functions $f(n)$ with

nonnegative integer input $n$ in the following pseudocode. Give the complexity in the form $O(g(n))$

for some function $g(n),$ and choose a bound as tight as possible $($e$.$g$.,$ if it is $O(n^3),$ then you

should write $O(n^3)$ instead of $O(n^4)).$ Justify your answers. Note that $"$a $\%b^{?}$ computes the

remainder of a when divided by $b,$ and $"ab"$ returns whether $ab.($Also note that the

time complexity of $f(n)$ may or may not be the same as the value of $f(n).)$

$($a$)(5pts)$

function f$($n$)$:

for i $=1,,.,$ n:

for j$\}=1,,$i

print$($i $+$ j$)$

$($b$)(5pts)$

function f$($n$)$:

if n:

return $1$

else:

return $($f$($n$-1)+$f$($n$-1)+$f$($n$-2))\%10$

$($c$)(5pts)$

function f$($n$)$:

if n:

return $1$

else:

a $=0$

for i $=1,,$ n:

a $=($a$+$i$)\%10$

return $($a $+$ f$($floor$($n$/2)))\%10$

Note that floor$(\frac{n}{2}$ computes ${|}_{{?}_{?}}\frac{n}{2_{{?}_{?}}}|.$

$($Hint: Let the running time of $f(n)$ be $T_n.$ First compute $T_{2^k}$ for integer $k0.$ Then

prove by induction that $T_n$ is nondecreasing, i$.$e$.,T_n{T}_m$ for $nm.$ Finally, we have

$T_n{T}_{2^k}$ where $k=|$~$lo{g}_{2}n$~$|lo{g}_{2}n+1.)$