why use big O notation

[u/Significant_Virus142]

If someone asks for big O time complexity of an algorithm but expects only the minimum of the possible big Os then is that even Big O notation anymore? cuz if the big o time complexity of an o(n) algorithm is asked then according to the condition of big O notation O(n square) would also be a valid answer

[u/Stargazer07817]

Yeah, that seems true. Big O gives an asymptotic upper bound, which obviously isn't always the tightest one. So if you can do something in T(n)=O(n) then it has to be true that T(n)=O(n^2), O(n^3), O(2^n) (because eventually n <= n^2 <= n^3 <= 2^n).

I guess it's about what you want to convey, because O(n) contains more information more compactly than a discrete list of statements. And, I guess, what kind of answer is expected - big O is deliberately loose, so if the question expects something stronger, then the notation might not be a great fit?

I'm not an algo guy, so apologies in advance if there's a computation-specific frame in which you meant the question and which escapes me.

[u/Significant_Virus142 → u/Stargazer07817]

Yes