[scott_s]

I literally meant n^n, which is also what I assumed sadga meant. That is, an upper bound which allows for absurdly fast growth.

I have discussed matrix multiplication's unknown lower bound with theorists, but more as a trivia item because there is a relatively recent result showing that it is O(n^2.3727) (http://www.cs.berkeley.edu/~virgi/matrixmult.pdf). That is, the unknown lower bound was the point of the conversation, and it was interesting because the lower and upper bound are not the same; it's still open research. The other point the theorist made during that conversation is similar to what I've said: getting a tighter bound on matrix multiplication is theoretically interesting, but there's not much practical application.

I was rather talking about when we discuss algorithm when trying to solve problems.