Find the Computational Complexity

When speaking of the runtime of an algorithm, it is conventional to give the simplest function that is AsymptoticEqual (big ) to the exact runtime function. Another way to state this equality is that each function is both AsymptoticLessEqual (big ) and AsymptoticGreaterEqual (big ) than the other. These concepts are illustrated in the context of Strassen's algorithm, the first subcubic matrix multiplication algorithm found.

The algorithm consists of four steps: splitting each of the matrices into 4 submatrices, forming 14 linear combinations from the 8 submatrices, multiplying 7 pairs of these and summing the 7 results. The time to do the multiplication will therefore be a constant time to split the matrix, for forming linear combinations in the second and fourth steps and for the third step.

Solve the recurrence relation.

Though the result is complicated, .

Equivalently, and .

Note that , so the algorithm is subcubic.

Compare the rate of growth of the naive cubic algorithm and Strassen's algorithm.

Related Examples

de es fr ja pt-br zh