Code Code Code Blog

When you pick a random developer and you ask him, hey, what is the time complexity lower bound for a search algorithm, the answer, which has become today almost a reflex is O(nlgn) which is also called linearithmic.  If you search Wikipedia for the running time of radix sort it's saying hold to your chair, O(n), how could that be you ask? It makes a few assumptions and does it more efficiently, it's trick is that the look and peek into the keys themself s, and then it manages to be a non comparison based algorithm.  So while it's true that the lower bound of search algorithms which are based on comparisons is O(nlgn) for non comparison based (such as radix sort) it's O(n) If you have the array already sorted we could say that our running time for sorting the array is O(1), so aren't we tricking reality, the difference is that the O(n) on radix sort holds also for a non-sorted array. Examples of sorts which are comparison based sorting algorithms are all the us...