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.