[omaranto]

About: "In discussions with a theorist, they would never tell me that something is O(n^n) if it is not also Θ(n^n)". So you've never heard someone say, for example, that Strassen's algorithm shows that matrix multiplication for n x n matrices can be done with O(n^2.808) multiplications?

For some problems, the best known upper bounds don't match the best known lower bounds. Also, in cases where there are further improvements in the upper bounds, it doesn't automatically mean people stop talking about previous upper bounds.

(Ignore this whole comment if you specifically meant the function n^n, I have no examples relevant to that function.)

[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.