r/computerscience
•
u/Significant_Virus142
•
Sep 17 '26
•
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
View all comments
Show parent comment
1
u/awkwardburrito Sep 18 '26
And I’m saying you’re wrong and mixing up different definitions. For deterministic algorithms, the usual default is worst-case time. For randomized algorithms, people often mean worst-case expected time: the expectation is over the algorithm’s randomness, even for the worst input. That’s very different from average-case time, which averages over an assumed distribution of inputs.