Hacker News new | ask | show | jobs
by tsimionescu 1523 days ago
No, not really. CS and other branches of maths are using the exact same definitions of O,o,Θ, and ω. It is true that Ω is used with a different definition in CS, but it's stricter not more slack.

As explained elsewhere though, they are not notations for algorithmic complexity, they are notations for function categorization. It just happens that a common use for this notation in CS is to categorize the function "best/average/worse/... case complexity of an algorithm", but they are also used for other purposes.

1 comments

In my experience, a lot of the time when programmers say big O, they actually mean big Theta...
Programmers need not be very good computer scientists. The actual scientists publishing papers on algorithms usually get it right.
Yes, I agree with that. However, if f(n)=Theta(n) => f(n)=O(n), so they are usually not wrong, technically, just unnecessarily broad.