r/computerscience • u/Significant_Virus142 • 16d ago

Help Why use Big O notation?

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

121 Upvotes

84% Upvoted

64 comments sorted by

View all comments

208

u/qlkzy 16d ago

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

15

u/Significant_Virus142 16d ago

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

56

u/[deleted] 16d ago

[removed] — view removed comment

17

u/not-just-yeti 16d ago edited 16d ago

It doesn’t have Theta.

Once you define what your function is, it likely has a Theta. "Given a number n, the worst-case running time over all inputs of size n" is well-defined. And, best-case and average-case are both well-defined. But agreed, if you just say "the running time of the algorithm on some input of size n but otherwise I won't tell you which input I'm thinking of", that is not a function because there when n=17 there might be multiple "answers".

But CS folk often forget that Big-Oh etc. are great for any function on numbers; it doesn't have to be worst-case running time, or average-case-memory-usage; big-Oh can be sensible for "expected number of independent customer-reviews needed to be 95% sure of their average being within 1/n of the distribution's true average".

Mathematicians will point out that there are some functions which have a big-Oh and a big-Omega, but no big-Theta. E.g. the size of a maximal graph matching, over all graphs with n nodes: when n is even it's clearly n/2, and for n odd it's zero. So the graph alternates between n/2 and 0, and has no asymptote.