HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

Strassen algorithm for matrix multiplication complexity analysis

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
strassenmultiplicationanalysisalgorithmformatrixcomplexity

Problem

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

Solution

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.

Context

StackExchange Computer Science Q#101638, answer score: 13

Revisions (0)

No revisions yet.