$2.$ Write a recurrence relation describing the worst case running time of each algorithm.

Solve the recurrence relation to determine the asymptotic complexity. In each, you may

assume that $0<=$ n $<=$ len$($xs$).$ Also, the double$-$divison notation a$//$b evaluates to the

integer $$a$/$b$.$ We SHOULD NOT use the Master theorem

$($a$).$

$1$ def f$1($xs$,$ n$)$:

$2$ if n $<10$:

$3$ return xs$[$n$-1]$

$4$

$5$ x $=0$

$6$ for i in range$(10)$:

$7$ for j in range$($n$)$:

$8$ xs$[$j$]=$ xs$[$j$]-$ xs$[$i$]$

$9$

$10$ x $=$ x $+$ f$1($xs$,$ n$//10)$

$11$ return x

$($b$)$

$1$ def f$2($xs$,$ n$)$:

$2$ if n $<5$:

$3$ return xs$[$n$-1]$

$4$

$5$ if xs$[0]<$ xs$[$n$-1]$:

$6$ return xs$[1]+$ f$2($xs$,(2*$n$)//3)$

$7$ else:

$8$ return xs$[2]-$ f$2($xs$,$ n$//5)$

$($c$)$

$1$ def f$3($xs$,$ n$)$:

$2$ if n $<5$:

$3$ return xs$[$n$-1]$

$4$

$5$ i $=$ n $-3$

$6$

$7$ x $=0$

$8$ while i $>$ n$//2$:

$9$ for j in range$($n$//2)$:

$10$ xs$[$j$]=$ xs$[2*$j$]-$ xs$[$i$]$

$11$ x $+=$ f$3($xs$,$ i$)$

$12$ i $-=12$

$13$ return x