how that two $2\backslash$times $2$ matrices can be multiplied using $4$ additions and $8$ multiplications.

$($b$)$ Show that for all i $<$ n$,$ all entries of Xi have O$($n$)$ bits. $($Hint: Consider the effect of each matrix

multiplication on the bit count$).$

$($c$)$ The following recursive algorithm can be used to efficiently compute Xn$.$

Show that the running time of this algorithm is O$($M$($n$)$ log n$),$ where M$($n$)$ is the time it takes to

multiply two n$-$bit numbers. $($Hint: first show that there are O$($log n$)$ recursive calls, and then show

each call takes at most O$($M$($n$)),$ you may use the results of parts $($a$)$ and $($b$)$ to show the latter$).$