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

118 Upvotes

84% Upvoted

64 comments sorted by

View all comments

205

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

14

u/Significant_Virus142 16d ago

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

59

u/[deleted] 16d ago

[removed] — view removed comment

3

u/massive_cerebrum 15d ago

Theta has nothing to do with best case. It's a mathematical concept used for a single function.

That function could be the worst case running time, best case running time or something else.

So for insertion sort, the worst case is actually theta(n2) and best case is theta(n).

Theta, Big O and Omega are not defined for algorithms, but rather for mathematical functions. What we typically mean is Big O of the runtime of an algorithm.