3 ms·
Strassen's algorithm is, I think, one of the easier ones to understand along these lines. It uses a recursive divide and conquer strategy. The naive algorithm
by klyrs 3y ago
Strassen's algorithm is, I think, one of the easier ones to understand along these lines. It uses a recursive divide and conquer strategy. The naive algorithm does 1 (N x N) multiplication by adding the results of 8 multiplications of size (N/2 x N/2), and (sweeping details under the rug here) that takes time N^log2(8) = N^3. The improved algorithm uses 7 multiplications of size (N/2 x N/2) and takes N^log2(7). For those details, the wiki page does a nice job.
https://en.m.wikipedia.org/wiki/Strassen_algorithm https://en.m.wikipedia.org/wiki/Strassen_algorithm
So intuitively speaking: when I see a logarithm like that with an integer ratio, I think "oh, somebody saved 1/6th of the work in a recursive algorithm."
- dataflow 3y agoThis is a power of a logarithm though? Whereas you're talking about the base and its argument.
- klyrs 3y agoNo, Strassen's isn't an exact match in this case. Just an example how strange exponents can crop up in complexity analysis. I was aiming to satisfy the original comment's ask for "intuition" rather than "read the entire paper and digest it in time to make an unassailable ELI5 while waiting for the bus."
- dataflow 3y agoThis isn't just "an exponent" though, it's a double exponent on a logarithm that is in the first exponent. It sure looks like a radically different beast than the recursion or the Master theorem. The mere presence of strange numbers in some exponent really doesn't say anything - I doubt anyone derives any intuition from the Strassen case, since as I'm sure you can imagine, algorithms that take n^(5/6) time, vs. (log n)^(5/6) time, vs. n^(log (5/6)) time, vs. n^((log n)^(5/6)) time... really need not have any common intuition behind them whatsoever.
- klyrs 3y agoReally leaning into that "somebody's wrong on the internet" thing, aren't you. If you have a better example that has exactly the right runtime and admits a simple description, feel free to share with the class.