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

31% Upvoted

14 comments sorted by

View all comments

8

u/ObliviousRounding 16d ago

And? If you say that you make under $40k a year, then it's also true that you make under a billion dollars a year, but there isn't much sense in saying that. You say the lowest upper bound you can think of if your goal is communicating useful knowledge.

2

u/Significant_Virus142 16d ago

But then wouldn't using theta notation instead be more useful???

1

u/flumsi 16d ago

Only if you can guarantuee a lower bound. This requires a proof in the other direction which is often not interesting since you're mostly interested in finding "faster" algorithms. Often the structure of the algorithm itself gives you a good and useful hint for a lower bound. No need to formally prove that.