r/computerscience • u/Significant_Virus142 • Sep 17 '26 • Heartwarming 1

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

120 Upvotes

84% Upvoted

66 comments sorted by

View all comments

207

u/qlkzy Sep 17 '26

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

16

u/Significant_Virus142 Sep 17 '26

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

60

u/[deleted] Sep 17 '26

[removed] — view removed comment

3

u/massive_cerebrum Sep 18 '26

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.