5 ms·
Big O notation is about the theoretical upper bound of an algorithm. Clever data-based tricks like putting items in buckets or gathering statistics are unrelate
by lemagedurage 7y ago
Big O notation is about the theoretical upper bound of an algorithm. Clever data-based tricks like putting items in buckets or gathering statistics are unrelated to this notation as they rely on a certain consistency. Maybe you should call it average run time on typical data.
- loeg 7y agoGP is talking about radix sort, basically. If you know all your keys are integers you can sort in O(n log k) (k is maximal key width in bits).
- joshuamorton 7y agoYou have a bit of a repetition here backwards. You can sort in O(n * k), where k is the maximal key width in bits. This ends up being O(n log(k)). Your formulation suggests radix sort running in O(n log(log(k))), which isn't quite true.
- loeg 7y agoSorry, my mistake -- you're totally right. Number of bits is log_2(k), where k is just the maximal key number.
- nwallin 7y agoRadix sort is worst case O(n). (which is what I'm assuming the parent commenter is referring to) It's not n in common situations, but nlogn in pathological cases the way Timsort is. The reason is it "violates" the n logn lower bound of comparison sorts is because it isn't a comparison sort. Sort of like how hash table lookups "violate" the O(log n) average lower bound of binary tree lookups. It has different performance bounds because it's a different problem.
- joshuamorton 7y agoNo, radix sort is worst case O(n * k). In many common cases, k ~= log(n). IN certain specific cases, k < log(n), and specifically for cases where you have a very large n, but a bounded number of values (say, you're sorting 10 billion 4-bit ints), k can be considered a constant. But that is by no means generally true.
- bloomer 7y agoIn most cases k << n. For 64-bit integers, byte wise radix sort k is 8, which is less than log n whenever n is more than 256. So, radix sort is typically much faster than an O(n log n) sort of your data support it. It just isn’t as widely used because it is not as general as a comparison based sort.
- joshuamorton 7y agoAfter a byte-wise radix sort you still have to sort within each bucket. In the worst case, every element falls into a single bucket, at which point your best best is to do a bit wise radix sort over the low 8 bits. This ends up being equivalent to k=log(n).
- gigatexal 7y agoJumping in this fascinating thread about sorting to ask what the double less than chevrons mean? I know what one means but what do two of them mean?
- oh_sigh 7y agohttps://www.google.com/search?q=what+does+<<+mean https://www.google.com/search?q=what+does+<<+mean
- Spiritus 7y agoBasically “much less than”.
- donbindner 7y agoIn this context, it means "much less." It's used that way sometimes in mathematical discussions.
- pdpi 7y agoThe n log n bound is for comparison sorts, which Radix Sort is not an instance of.