4 ms·

This is a power of a logarithm though? Whereas you're talking about the base and its argument.

• klyrs 3y ago
  No, 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 ago
    This 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 ago
      Really 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.