8
$\begingroup$

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).$$

$\endgroup$
13
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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})$.

$\endgroup$
0
$\begingroup$

Time complexity is often based on the input size, but it is not an absolute requirement. In this case, for the multiplication of n x n matrices, it seems most natural to count the number of operations based on n, not on the problem size n x n.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.