Umm, AKCTSHUALLY it gets more like O(n^2^) in parallel, assuming you’re using a physically achievable memory. There’s just a lot of criss-crossing the entries have to do.
Strassen’s algorithm gets O(n^2.8^) in serial by being terrible, and the weird experimental ones get O(n^2.3^), but the asymptotic benefits of Coppersmith-Winograd and friends only kick in if you’re a Kardashev III civilisation computing a single big product on a Dyson sphere.
Yeah, they work by turning the problem into some crazy kind of group theory and attacking it that way. Every once in a while someone shaves the decimal down slightly, just by implementing the deep math in a more efficient way. A new approach will be needed if it is in fact possible to get down to O(n^2^), though. Strassen’s is a divide and conquer algorithm, and each step of the iteration looks like this:
In my copy of Introduction to Algorithms, it says something like “this is the most bullshit algorithm in the book and it’s not close” underneath. You can make it a bit neater by representing the multiplication operation as a 3-dimensional tensor, but at the end of the day it’s still just a stupid arithmetic trick. One that’s built into your GPU.
I can’t decide whether this sentence is a joke or not. It has the same tone that triggers my PTSD from my CS degree classes and I also do recognize some of the terms, but it also sounds like it’s just throwing random science terms around as if you asked a LLM to talk about math.
That’s a huge leap from O(n²) to O(n), in this example it would likely good to at least specify that it should be strictly less than best known solution (not sure if there are such cases on leet code, I thought they only restrict you to what is known to be solvable)