World's most popular travel blog for travel bloggers.

[Solved]: Why can't hash tables provide O(n) sorting?

, , No Comments
Problem Detail: 

Since a sufficiently large hash table takes constant time to both insert and retrieve data, should it not be possible to sort an array by simply inserting each element into the hash table, and then retrieving them in order?

You just insert each number into the hash table, and remember the lowest and highest number inserted. Then for each number in that range, in order, test if it is present in the hash table.

If the array being sorted contains no gaps between values (i.e. it can be [1,3,2] but NOT [1,3,4]), this should give you O(N) time complexity.

Is this correct? I don't think I've ever heard of hash tables being used this way - am I missing something? Or are the restrictions (numeric array with no gaps) too much for it to be practically useful?

Asked By : Benubird

Answered By : David Richerby

The algorithm you give is exponential time, not linear. If you're given $n$ $b$-bit entries, the size of your input is $nb$ bits but the algorithm takes time $\Theta(2^b)$, which is exponential in the input length. In particular, your algorithm takes $2^k$ steps to sort the roughly $2k$-bit input $\{0, 2^k\}$.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback