2 ms·
You 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 formulat
by joshuamorton 7y ago
You 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.