4 ms·
Yea, it's linear time for n where n is the largest number—pretty sure it's unbounded in terms of numbers of elements.
by duaneb 12y ago
Yea, it's linear time for n where n is the largest number—pretty sure it's unbounded in terms of numbers of elements.
- bnegreve 12y agoTrue, but writing a linear sort with bounded number of distinct elements is not really a challenge. E.g. Intput, T: array of n elements, m: number of distinct elements. for i in 1..m for j in 1..n if( T[j] == i ) print T[j]; This is O(n * m) which is O(n) since m is a constant.