Talk:TADM2E 4.25
From Algorithm Wiki
I don't agree with that the time complexity is $ O(n) $ of the first step.
The array $ A' $ has $ x $ numbers. If you want to find a number, you can do it in O(x), cause the array is not in order. Creating there two arrays can be done in $ O(xn) = O(nloglogn) $.
Finally, the array can be sorted in $ O(nloglogn) $.
