3 ms·
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
by tsimionescu 5y 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.
- ufo 5y agoIn my experience, a lot of the time when programmers say big O, they actually mean big Theta...
- adrianN 5y agoProgrammers need not be very good computer scientists. The actual scientists publishing papers on algorithms usually get it right.
- tsimionescu 5y agoYes, I agree with that. However, if f(n)=Theta(n) => f(n)=O(n), so they are usually not wrong, technically, just unnecessarily broad.