Talk:TADM2E 4.25

From Algorithm Wiki
Revision as of 01:34, 28 April 2015 by James Shi (talk | contribs) (Created page with "I don't agree with that the time complexity is <math>O(n)</math> of the first step. The array <math>A'</math> has <math>x</math> numbers. If you want to find a number, you ca...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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).