patternMinor
How does one end up with a non-integer exponent in time complexity? (e.g., $O(n^{2.81})$)
Viewed 0 times
exponenthownonwithtimeonedoesendintegercomplexity
Problem
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?
"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?
Solution
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.
$$
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.
Context
StackExchange Computer Science Q#22468, answer score: 9
Revisions (0)
No revisions yet.