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.