Problem $1$: Give an asymptotic estimate, using the $-$notation, of the number of letters printed by the

algorithms given below. Give a complete justification for your answer, by providing an appropriate recurrence

equation and its solution.

$($c$)$ algorithm PrintCs $(n)$

if $n2$ then

print $("$C$")$

else

for jlarr$1$ to $n^3$

do print$(4$ C$")$

$Pr{\displaystyle \underset{\phantom{}}{\overset{\phantom{}}{}}}Cs({|}_{{?}_{?}}\frac{n}{3_{{?}_{?}}}|)$

$Pr{\displaystyle \underset{\phantom{}}{\overset{\phantom{}}{}}}Cs({|}_{{?}_{?}}\frac{n}{3_{{?}_{?}}}|)$

$Pr{\displaystyle \underset{\phantom{}}{\overset{\phantom{}}{}}}Cs({|}_{{?}_{?}}\frac{n}{3_{{?}_{?}}}|)$

$Pr{\displaystyle \underset{\phantom{}}{\overset{\phantom{}}{}}}Cs({|}_{{?}_{?}}\frac{n}{3_{{?}_{?}}}|)$

$($d$)$ algorithm $Pr{\displaystyle \underset{\phantom{}}{\overset{\phantom{}}{}}}Ds(n)$

if $n5$ then

print$("$D$")$

$pr{\displaystyle \underset{\phantom{}}{\overset{\phantom{}}{}}}(D)$

$pr{\displaystyle \underset{\phantom{}}{\overset{\phantom{}}{}}}(D)$

if $(x-=0(mod2))$ then

PrintDs $({|}_{{?}_{?}}\frac{n}{5_{{?}_{?}}}|)$

PrintDs $(|$~$\frac{n}{5}$~$|)$

xlarrx$+3$

else

$Pr{\displaystyle \underset{\phantom{}}{\overset{\phantom{}}{}}}Ds(|$~$\frac{n}{5}$~$|)$

PrintDs $({|}_{{?}_{?}}\frac{n}{5_{{?}_{?}}}|)$

xlarr$5x+3$

In part $($d$),$ variable $x$ is a global variable initialized to $1.$