9
$\begingroup$

Periodically I come across sentences like

"Winograd's variant [20] of this algorithm, whose asymptotic complexity is also $O(n^{2.81})$ are considered" (from https://www.cise.ufl.edu/~sahni/papers/strassen.pdf)

I understand intuitively how we end up with complexities like $O(n^2)$ and $O(n \log n)$ because I can see how the loops and trees work. But I've got no idea of how one ends up deriving a complexity with a decimal. Can someone give me an example how this happens?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
9
$\begingroup$

The running time complexity of Strassen's algorithm is given by the recurrence $$ T(n) = 7T(n/2) + O(n^2). $$ (With a suitable base case.) The solution of this recurrence is $T(n) = O(n^{\log_2 7})$.

Strassen's algorithm multiplies two $n \times n$ matrices $A,B$ by decomposing them into four $(n/2)\times(n/2)$ matrices each, computing seven linear combinations of the smaller matrices each, say $(A_i,B_i)_{i=1,\dots,7}$, recursively computing $C_i = A_i B_i$, and computing the four $(n/2)\times(n/2)$ matrices of the result by taking linear combinations of the matrices $C_i$. That's how this running time came to be. If you want to learn more, there is a lot of information out there on Strassen's algorithm. There are, by the way, asymptotically faster algorithms for matrix multiplication, the current champion being Le Gall.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I think I'm looking for the answer - 'you get a decimal, in this case, by solving this recurrence relation.' - I'm actualy trying to ask a slightly more general question about circumstances where this happens. Is a recurrence relation the only possible way that one would get a non-integer exponent? $\endgroup$
    – Joe
    Mar 10, 2014 at 18:51
  • 1
    $\begingroup$ There are other ways. For example, in network flow algorithms, some iterative algorithm might converge in $\sqrt{n}$ steps. Other examples are Chebyshev polynomials, which behave "like" polynomials of degree $d$ but have degree $\sqrt{d}$. There could be more examples, and in any case there is no reason for any list to be exhaustive – new ideas come up all the time. $\endgroup$
    – Yuval Filmus
    Mar 10, 2014 at 19:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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