Why is Big-Oh notation useful when it's so easy to find a technically correct Big-Oh of most algorithms?

Question

My understanding is that if an algorithm is O(1) it is also O(n), O(n^2), O(n^3) and so on which makes it seem useless. For example, if someone asked me for the Big-Oh notation of any algorithm, I could just say O(n^n) without thinking about it (literally) and be technically correct most of the time.

Since (it's my understanding that) this is true, how is this useful information? To use an analogy, if I asked someone how many houses they own, an answer like, "1 to infinity" isn't very informative. A useful answer (this is kind of like Big-Theta) would be "1".

Answer 1

Saying any algorithm is O(n^n) is not correct, because big-Oh refers to a tight upper bound. We also do not say an algorithm is O(n^n), but rather the algorithm's time complexity is in O(n^n).

I hope this clarifies things.

Answer 2

Here's a letter by Donald Knuth for proposing the O notation to American Mathematical Society

Answer 3

Big-O establishes an upper bound. If you know that an algorithm is O(n²) then you know its complexity is at worst quadratic. It could in fact be O(n) or O(1) but it's definitely not O(n³). It's very useful to figure out upper bounds on runtime for algorithms.

You are correct that the question, "What's the Big-O of this algorithm?" is poorly worded. The word "the" is incorrect. There's no one Big-O of an algorithm. There are many. Infinitely many. Big-O does not establish a tight upper bound. That's where Big-Theta comes in. Big-Theta asserts both an upper and lower bound: it gives an exact asymptotic bound. The question should be, "What's the Big-Theta of this algorithm?"

But it's important not to throw Big-O out, because not all algorithms have exact bounds known. Matrix multiplication is a well known problem that doesn't have an established Big-Theta. The naive algorithm is O(n³) and the state-of-the-art is O(n^2.3727). That's an upper bound but it's probably not the (optimal) upper bound. Big-Theta lies somewhere between O(n^2.3727) and Ω(n²).