Recall the Karatsuba or Cook$-$Toom $m_2$ algorithm from class that can multiply two $n-$bit integers in $O(n^{1\mathrm{.}585}).$ We will call this algorithm MultiplyKS.

The following algorithm returns the result of $3^y$ where $y$ is an integer such that $y0.($a$)(8$ points$)$ Prove this algorithm is correct using induction.$($b$)(3$ points$)$ If y$=2^($k$)$ for some integer k $>=0,$ Write a recurrence relation for the number of recursive calls before the algorithm terminates $($in terms of k$.)($c$)(4$ points$)$ Calculate the asymptotic runtime of the algorithm using the master's theorem.