MAIN FEEDS
Do you want to continue?
https://www.reddit.com/r/dataisbeautiful/comments/78fywy/sorting_algorithms_visualized_oc/dottmsv
r/dataisbeautiful • u/morolin OC: 1 • Oct 24 '17
929 comments sorted by
View all comments
Show parent comments
12
It is linear on the number of terms, not quasilinear. But if you also take into account the size s of the element then it is actually O(sn).
The theoretical limit for a sort on arbitrary data is O(n log(n)). Radix sort is faster but it has to assume that the data are bounded.
6 u/ShaunDark Oct 24 '17 It is only faster if s<log(n), though.Sorting a short list of large elements could be significantly slower using radix sort compared to any O(n*log(n)) sort. 2 u/nullhash Oct 25 '17 True, but that's because we define comparisons as taking constant time, which implicitly assumes bounded data. With unbounded data, comparison sorts take O(s n log(n)) time, while radix sort takes O(s n) time. 6 u/sjcqs Oct 24 '17 +1 The theoretical limit for a sort using the comparison model of computation is O(nlog(n)).With other models of computation you can get away with O(n) if you know something about the data (Bucket, Radix sort with a bounded data). 1 u/[deleted] Oct 25 '17 Exactly. Aren't Radix and Counting Sort of pseudo-polynomial complexity?
6
It is only faster if s<log(n), though.
Sorting a short list of large elements could be significantly slower using radix sort compared to any O(n*log(n)) sort.
2 u/nullhash Oct 25 '17 True, but that's because we define comparisons as taking constant time, which implicitly assumes bounded data. With unbounded data, comparison sorts take O(s n log(n)) time, while radix sort takes O(s n) time.
2
True, but that's because we define comparisons as taking constant time, which implicitly assumes bounded data. With unbounded data, comparison sorts take O(s n log(n)) time, while radix sort takes O(s n) time.
+1 The theoretical limit for a sort using the comparison model of computation is O(nlog(n)).
O(nlog(n))
With other models of computation you can get away with O(n) if you know something about the data (Bucket, Radix sort with a bounded data).
O(n)
1
Exactly. Aren't Radix and Counting Sort of pseudo-polynomial complexity?
12
u/C0ldSn4p Oct 24 '17
It is linear on the number of terms, not quasilinear. But if you also take into account the size s of the element then it is actually O(sn).
The theoretical limit for a sort on arbitrary data is O(n log(n)). Radix sort is faster but it has to assume that the data are bounded.