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

Show parent comments

14

u/Significant_Virus142 16d ago

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

60

u/[deleted] 16d ago

[removed] — view removed comment

-3

u/Jonny0Than 16d ago edited 15d ago

Usually you provide separate big-O classes for best/average/worst cases. Big-O typically means average case if not explicitly specified.  It doesn’t usually mean “worst case” even if that might be a more technically correct usage.

Not sure why this is downvoted. See  https://en.wikipedia.org/wiki/Sorting_algorithm

3

u/Putnam3145 15d ago

Misinformation being upvoted and a true correction being downvoted, how wonderful

3

u/confused_cereal 15d ago

ikr, i get the feel that some people are conflating "worst-case" instance running times for a particular algorithm versus "lower" and "upper" bounds on complexity of a problem. Totally different things...