3 ms·
counting sort is O(nW), where W is largest value if you don't care about W or it is essentially constant - then it can be dropped but it is an input parameter
by NooneAtAll3 9mo ago
counting sort is O(nW), where W is largest value
if you don't care about W or it is essentially constant - then it can be dropped
but it is an input parameter that will change execution time
- emil-lp 9mo agoW is the span or range.
- marcosdumay 9mo agoIt's O(n+W), not O(n*W). > if you don't care about W or it is essentially constant - then it can be dropped Also, every algorithm that ends in a real computer is bound to a constant time. That's still not a practical thing to do.
- vlovich123 9mo agoThe simplification is correct but not correctly stated (even though colloquially it's common to state it that way). Technically it's when some component of the algorithm is dwarfed by another, then you can exclude it (i.e. O(n+W) =~ O(n) when W <<< n, O(mn) =~ O(n) when m <<< n etc). It's colloquially shortened to "when it's a constant" because generally it's constant regardless of program execution whereas the variable parts of the formula actually do change and thus the big-O analysis does still give you a correct lower bound on the performance. TLDR: You're being unhelpfully pedantic.