3 ms·
Computer scientists stole some notation from mathematicians, but then slightly changed and substantially slackened the definition...
by londons_explore 5y ago
Computer scientists stole some notation from mathematicians, but then slightly changed and substantially slackened the definition...
- tsimionescu 5y agoNo, 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.