6.

(a) What is the largest k such that if you can multiply 3 3 matrices using k multiplications, then you can multiply n n matrices in time o(n^LOG7)? What would the running time of this algorithm be? You can assume that n is a power of 3.

(b) V. Pan has discovered a way of multiplying 68 68 matrices using 132,464 multiplications, a way of multiplying 70 70 matrices using 143,640 multiplications, and a way of multiplying 72 72 matrices using 155,424 multiplications. Which method yields the best asymptotic running time when used in a divide-andconquer matrix-multiplication algorithm? How does it compare to Strassens algorithm?

PLEASE SHOW FULL STEPS EXPLAIN THINKING! AND ANSWER A &B SEPERATELY!