a$.(5$ points$)$ Prove the correctness of Alg$1$ using induction. $($Hint: $(1)$ does it work for $n=0?$

assuming it works for $n=i,$ can you show that it will work for $n=i+1?)$

b$.(15$ points$)$ Let $A(n),B(n),$ and $C(n)$ be the running time of the three algorithms, respectively, as a

function of $n.$ Write down the recurrences for $A(n),B(n),$ and $C(n).$

c$.($Extra credit: $15$ points$)$ Analyze and compare the running time of the three algorithms above. You

can use either recursion tree or master method to solve the recurrences.