28.2-4 V. Pan discovered a way of multiplying 68x68 matrices using 132,464 multiplications, a way of multiplying 70x70 matrices using 143,640 multiplications and a way of multiplying 72x72 matrices using 155,424 multiplications. Which method yields the best asymptotic running time when used in a divide-and-conquer matrix-multiplication algorithm? How does it compare to Strassen's algorithm?
(CLRS 2nd ed, p. 741)
Quando ele menciona "divide-and-conquer matrix-multiplication algorithm", ele se refere ao método "ingênuo" que necessita de 8 multiplicações de matrizes (com recorrência T( n ) = 8T(n/2) + ϴ(n²))? Ou temos que supor que o V. Pan é tão esperto quanto o Strassen e vai usar o método que faz só 7 multiplicações?
Porque se for para supor o método ingênuo, a segunda parte da questão fica bastante óbvia, pois os três métodos serão inexoravelmente ϴ(n³), enquanto que o Strassen é ϴ(n^lg7)... Ou entendi errado?