Originally Posted by

**Rashakil Fol** The way you are achieving O(n) complexity is not by avoiding comparisons, it's by arbitrarily limiting the number of distinct elements possible, giving yourself a counting problem, not a sorting problem. Sorting methods that do not use comparisons, while maintaining no restriction on the number of distinct elements, are still limited to O(n log n) performance, because they have to examine at least n*log(n)/log(2) bits in total simply to distinguish the elements from one another. The input size is effectively O(n log n).