The Algorithm Design Manual (3rd) Exercise Solution 'E4-36'

Introduction

This series is my solutions for algorithm exercises in'The Algorithm Design Manual' 3rd edition.
It's my solutions, not model answers, so if you find some mistakes or more sophisticated solutions, please post in comment area below.

Repository

Here

Exercise 4-36

Question

Assume that the array $A[1..n]$ only has numbers from $\{1,...,n^2\}$ but that at most log log n of these numbers ever appear. Devise an algorithm that sorts A in substantially less than $O(n \log {n})$.

Solution

First, we count the occurence of each number using hash table. Since the amount of the numbers existing in the array is considerably small, the procedure can be considered to take $O(n)$ time.

Then, we sort those numbers and arrange them by the number of their occurrences. This takes $O(\log{(\log{n})}\log{(\log{(\log{n})})})$ time.

So the overall time complexity is $O(n)$.