3 ms·
I think matrix multiplication is O(N^2.71), and there are a few problems in abstract algebra that have doubly exponential algorithms.
by banned_man 18y ago
I think matrix multiplication is O(N^2.71), and there are a few problems in abstract algebra that have doubly exponential algorithms.
- Retric 18y agoMatrix multiplication is a great example of this, there has been a lot of research into in sparse matrix multiplication because N^2.71 is still fairly difficult. Edit: There are a lot of known algorithms that would be extremely useful if they where faster.
- miloshh 18y agoYes, but that is for an N x N matrix. It is more useful to express the complexity in the size of the input, in which case matrix multiplication is N^1.5 or better. (As far as I know, the best known algorithm is pretty close to linear, but it's not known if a linear one exists.)