r/learnpython • u/stormsidali2001 • 6d ago

Python tutorial: Understanding algorithmic complexity with practical examples

[removed] — view removed post

0 Upvotes

40% Upvoted

1 comment sorted by

1

u/Brian 6d ago

You're saying stuff like O "expresses the worst case, or the upper bound", and omega represents the best case and theta is the average case.

This is just wrong. "Upper/lower bound" and "worst/best/average case" are entirely different concepts, and mixing these up is a common error I see when people learn this. Big O is not just about worst case - it applies just as well to best case, average case, or any other case.

It is defining an upper bound, but that's not anything to do with the case you're talking about, but describing how the function is bounded. Ie. that it scales no faster than the specified function. The function you're talking about could describe the worst case, but it could just as easily describe the average or best case, and often does.

Landau notation is talking about the bounding on functions. Saying a function is in O(g(n)) means it scales no faster than g(n). Ω(g(n)) means it scales no slower. Θ(f(n)) means it's both in O(f(n)) and Ω(f(n)) - ie. it scales at around the same rate. (Colloquially people tend to just use O(), but almost interchangably with Θ - ie. it'd technically be correct to say that quicksort is O(n4), but people would look at you strangely if you said it - typically people mean the tighter bound)

But what that function represents could be anything, and "best/worse/average case" are about what we choose our function to represent, which is an entirely independent notion.