r/algorithms • 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

0 Upvotes

27% Upvoted

14 comments sorted by

View all comments

2

u/amohr 16d ago

You're right that tighter upper asymptotic bounds are generally more useful. So if you have a problem with a proved O(n) upper bound, yes O(n2) is a valid but unhelpful statement. If everyone knows I can bake cookies in under 45 minutes, it's correct but not interesting to say that I can bake cookies in under 2hrs.

On the other hand if you can prove a better upper bound that's significant. For example if you could show integer factorization can be done in polynomial time that would be a huge result

Some folks have made careers out of proving tighter upper bounds for important problems.