Encontre a complexidade computacional

Quando se fala do tempo de execução de um algoritmo, é convencional fornecer a função mais simples AsymptoticEqual (big ) para a função exata de tempo de execução. Outra forma de afirmar essa igualdade é que cada função seja tanto AsymptoticLessEqual (big ) e AsymptoticGreaterEqual (big ) que a outra. Esses conceitos são ilustrados no contexto do algoritmo de Strassen, o primeiro algoritmo de multiplicação de matriz subcúbica encontrado.

O algoritmo consiste em quatro etapas: dividindo cada uma das matrizes em 4 submatrizes, formando 14 combinações lineares das 8 submatrizes, multiplicando 7 pares destes e somando os 7 resultados. O tempo para fazer a multiplicação será, portanto, um tempo constante para dividir a matriz, para formar combinações lineares no segundo e quarto passos e para o terceiro passo.

Resolva a relação de recorrência.

Embora o resultado seja complicado, .

Da mesma forma, e .

Note que , então o algoritmo é subcúbico.

Compare a taxa de crescimento do algoritmo ingênuo cúbico e do algoritmo de Strassen.