# Strassen algorithm for matrix multiplication complexity analysis

I see everywhere that the recursive equation for the complexity of Strassen alg is: $$T(n) = 7T(\tfrac{n}{2})+O(n^2).$$ This is not so clear to me. The parameter $$n$$ is supposed to be the size of the input, but it seems that here it is one dimension of a matrix while the input size is actually $$n^2$$. Also, each matrix of the input is divided to 4 sub matrices so it seems the recursive equation should be $$T(n) = 7T(\tfrac{n}{4}) + O(n).$$

It's true that the parameter $$n$$ usually denotes the size of the input, but this is not always the case. For square matrix multiplication, $$n$$ denotes the number of rows (or columns). For graphs, $$n$$ often denotes the number of vertices, and $$m$$ the number of edges. For algorithms on Boolean functions, $$n$$ denotes the number of inputs, though the truth table itself has size $$2^n$$. There are many other examples.
It's back to the size of the matrix. Suppose the original matrix is $$n\times n$$. Hence we will consider $$T(n)$$ as a computation of two matrix with size of $$n\times n$$. When we divide the original matrix to 4 part, size of each part is $$\frac{n}{2}\times \frac{n}{2}$$. Hence, the computation cost of multiplication of two matrices with this size is $$T(\frac{n}{2})$$.