Efficiency
Radix sort's efficiency is O(k·n) for n keys which have k or fewer digits. Sometimes k is presented as a constant, which would make radix sort better (for sufficiently large n) than the best comparison-based sorting algorithms, which are all O(n·log(n)). However, in general k cannot be considered a constant. In particular, under the common (but sometimes implicit) assumption that all keys are distinct, then k must be at least of the order of log(n), however other sorting methods become O(log (n) * log (n) * n) under similar constraints as they also need to step through an ever increasing number of symbols to do the comparisons.
Read more about this topic: Radix Sort
Famous quotes containing the word efficiency:
“Nothing comes to pass in nature, which can be set down to a flaw therein; for nature is always the same and everywhere one and the same in her efficiency and power of action; that is, nature’s laws and ordinances whereby all things come to pass and change from one form to another, are everywhere and always; so that there should be one and the same method of understanding the nature of all things whatsoever, namely, through nature’s universal laws and rules.”
—Baruch (Benedict)
“I’ll take fifty percent efficiency to get one hundred percent loyalty.”
—Samuel Goldwyn (1882–1974)
““Never hug and kiss your children! Mother love may make your children’s infancy unhappy and prevent them from pursuing a career or getting married!” That’s total hogwash, of course. But it shows on extreme example of what state-of-the-art “scientific” parenting was supposed to be in early twentieth-century America. After all, that was the heyday of efficiency experts, time-and-motion studies, and the like.”
—Lawrence Kutner (20th century)