3 ms·
O(n+n * log(w/log(n)) ) Wouldn't this decrease again for large enough n, and even go negative after n=2^(w * 2)?
by 1wd 6y ago
O(n+n * log(w/log(n)) )
Wouldn't this decrease again for large enough n, and even go negative after n=2^(w * 2)?
- dan-robertson 6y agoThe algorithm is to switch to a counting sort when w <= log n, ie n >= 2^w, so more properly the complexity is written: O(n+max(0,log(w/log n)))
- rocqua 6y agoNot sure whether it applies here, but _if_ n is the number of unique values, you are limited here by the fact that there are only 2^w unique integers. Hence n < 2^w
- karpierz 6y agoThe recursion assumes that log(n) > w; if log(n) <= w, then you're in the base case and it's O(n).
- deleted 6y ago[deleted]
- ben-schaaf 6y agoNot sure what's going on here, but that does indeed seem to be the case: https://www.wolframalpha.com/input/?i=x%2Bx+*+log%282%2Flog%28x%29%29+%3D+0 https://www.wolframalpha.com/input/?i=x%2Bx+*+log%282%2Flog%...