V. Pan has developed a way to multiply matrices of size 68 by 68, using 132,464

Question

V. Pan has developed a way to multiply matrices of size 68 by 68, using 132,464 multiplications (I won’t tell you how many additions), a way to multiply 70 by 70 matrices with 143,640 mults., and a way to multiply 72 by 72 matrices with 155,424 mults. These methods can be used recursively to multiply two matrices of dimension n by n. In the first case we can assume that the dimension of a matrix is a power of 68; in the second case it is a power of 70; and in the third case it is a power of 72. When used recursively, work out the assymptotic number of operations each of these methods does, as a function of n. You will need a good calculator or a computer for this. Which of these methods yield the best asymptotic running time when used recursively for large matrices?

Explanation / Answer

>>>>>>
For each case, we write the recurrence and solve it using the master theorem:

(1) T ( n ) = 132464 T ( n/ 68) + n2 T ( n ) = ( n log68132464 ) ( n2 . 795128 )
(2) T ( n ) = 143640 T ( n/ 70) + n2 T ( n ) = ( n log 70 143640 ) ( n2 . 795123 )
(3) T ( n ) = 155424 T ( n/ 72) + n2 T ( n ) = ( n log 72 155424 ) ( n 2 . 795147 )
Strassen’s algorithm runs in ( n lg 7 ) ( n 2 . 81 ), so all these algorithms outperform Strassen

>>>>>
The algorithm is given an array of n numbers and a target number. The first two lines take
constant time, call it c . The next two lines recursively call Unsorted-Search on inputs of size
n/ 2. Therefore, the worst-case asymptotic complexity is
T ( n ) = 2 T ( n/ 2) + c
Using case 1 of the master theorem, we see that T ( n ) = ( n ).
This is the same worst-case asymptotic complexity as the naive algorithm, although in practice
the naive algorithm would probably run more quickly.

Related Questions

Navigate

• Browse (All)
• Browse V
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.