Problem $2.$ A classic matrix multiplication of two square matrices of size $nn$ takes $(n^3)$ time since each of the triply$-$nested for$-$loops runs exactly $n$ iterations. Consider a Divide$-$and$-$Conquer algorithm that computes the matrix product by assuming that $n$ is an exact power of $2$ in each of the $nn$ matrices. The recurrence for running this divide and conquer algorithm is given below. Give the asymptotic bound of this algorithm's running time.

Answer.

$T(n)=\{\begin{array}{ccc}(1)& if& n=1\\ 8T(\frac{n}{2})+(n^2)& if& n>1\end{array}$