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

Solve the recurrence relation to determine the asymptotic complexity.

$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