World's most popular travel blog for travel bloggers.

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

, ,
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?

#### 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\}$.