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.
