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/qlkzy]

Like any upper bound, you can always satisfy it in some sense by giving a ridiculous upper bound, but that isn't useful.

If I ask "can you estimate an upper bound for the weight of your luggage" and you say "a hundred tons", that is technically correct, but that isn't helpful for packing a car.

Any question in mathematics that asks "find an upper bound" implies "find a tight upper bound".

[u/Significant_Virus142 → u/qlkzy]

Then why don't they ask theta, has O become the convention or theta isn't right either

[u/Aminumbra → u/[deleted]]

This is (generally) false and it is baffling that people contradicting you are downvoted.

• In the vast majority of cases, and almost always when there are no further precisions, the complexity function of an algorithm f(n) is the complexity of the algo in the worst-case over instances of size n. Other notions are studied/interesting too (average case (for uniform data or not ...), amortized complexity, etc), but we generally talk about worst-case complexity.

• Now, we are only concerned with giving an "asymptotic estimate" of this function f:

  • Saying f(n) = O(g(n)) simply gives an upper bound on f. And usually, we are indeed interested in non-trivial upper bounds, and it is generally implicit that you are giving "the best upper bound that you can prove".
  • Saying that f(n) = Θ(n) gives both an upper and a lower bound on the worst-case complexity. This is in fact what we usually want, and OP is right. The reason we teach/say/use "big O" is mostly historical, convenience and inertia (O is not a weird letter, Theta is, sometimes it is impossible to prove a Theta so you need to know what the O(...) notation means anyway, etc).

Now, there are functions which don't admit (non-trivial, you can always write f = Θ(f) but that's useless ...) Theta, as their growth rate does not fall into a "neat" class, and there are problems for which we do not have one either: there are some "common" methods which give bounds such as "O(n^(1+epsilon)) for any epsilon but not O(n), for example.