Standard $16$: Analyzing Code III: Writing Recurrences

Problem $16.$ Write down a recurrence for the number of times this algorithm prints $$Hi$.$ Clearly justify

your answer. You are not being asked to solve the recurrence.

Algorithm $1$ Recurrences

$1$: procedure Merge$3$Sort$($List L$)$

$2$: if len$($L then return L

$3$: n $$ len$($L$)$

$4$: f irst $$ Merge$3$Sort$($L$[0$ : n$/3])$

$5$: second $$ Merge$3$Sort$($L$[$n$/3$ : $2$n$/3])$

$6$: third $$ Merge$3$Sort$($L$[2$n$/3$ : n$])$

$7$: for i $1$; i n; i $$ i $+1$ do

$8$: print $$Hi$//$ This loop doesn$$t actually do anything! But has the same runtime as a $3-$way merge

$9$: return L

Answer$16$ Standard $16$: Analyzing Code III: Writing Recurrences

Problem $16.$ Write down a recurrence for the number of times this algorithm prints $"$Hi$".$ Clearly justify

your answer. You are not being asked to solve the recurrence.

Algorithm $1$ Recurrences

procedure MERGE$3$SoRT$($List $L)$

if len$(L)1$ then return $L$

nlarrlen$(L)$

second larrMerge$3$Sort$(L[\frac{n}{3}$:$2\frac{n}{3}])$

third larrMerge$3$Sort$(L[2\frac{n}{3}$:$n])$

for ilarr$1$;$in$;ilarri$+1$ do

print $"$Hi$"//$ This loop doesn't actually do anything! But has the same runtime as a $3-$way merge

return $L$