In this question, you will prove the Master Theorem in the special $($and most important$)$ situation when f$($n$)=$ n$^($z$)$ for some real number z$.$

This result enables us to determine tight asymptotic bounds for various recurrence relations, which will help us tremendously in algorithm design and algorithm analysis.

If you can reproduce the proof of this result, then you will understand how the Master Theorem works in all situations $-$ e$.$g$.$ when f$($n$)=4$n$^(3)+2$n$^(2)$ logn $+5$n $+100$logn $+777.$ But for the purposes of this problem, we will assume f$($n$)=$ n$^($z$).$

Let x$,$y$,$z be real numbers for which T$(1)=1$ and T$($n$)=$ xT$(($n$)/($y$))+$ n$^($z$).$

$($a$)$ If z $<$ logy$($x$),$ prove that T$($n$)=\backslash$theta $($n$^(\backslash$log $\_($y$)$x$)).$

$($b$)$ If z $=\backslash$log $\_($y$)$x$,$ prove that T$($n$)=\backslash$theta $($n$^(\backslash$log $\_($y$)$x$)\backslash$log $\_($y$)$n$).$

$($c$)$ If z $>$ logy$($x$),$ prove that T$($n$)=\backslash$theta $($n$^($z$)).$

$($a$)$ Some of you have taken a course in Linear Algebra, a core course in an undergraduate mathematics curriculum. In this course, students learn how to multiply two n by n matrices, and one can easily design an algorithm to perform matrix multiplication, running in $($n$^3)$ time.

In $1969,$ Volker Strassen developed a recursive method to perform matrix multiplication, where the running time T$($n$)$ can be given by the recurrence relation T$($n$)=7$T$($n$/2)+$ n$^2.$

Using any of the results in $($a$),($b$),$ or $($c$),$ determine the running time of Strassen$$s Algorithm and show that it is faster than the standard algorithm that runs in $($n$^3)$ time.

Note: if you are unable to prove $($a$),($b$),($c$)$ in its general form, you are welcome to instead solve the following simplified version of the problem, where you let y $=2$ and x $=16,$ and prove the result for z $=3$ in part $($a$),$ z $=4$ in part $($b$),$ and z $=5$ in part $($c$).$ If your proof is correct, you will be given $10$ marks for solving the simplified version of the problem.