Difference between revisions of "Talk:TADM2E 4.25"
From Algorithm Wiki
(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...") |
|||
| Line 4: | Line 4: | ||
Creating there two arrays can be done in <math>O(xn) = O(nloglogn)</math>. | Creating there two arrays can be done in <math>O(xn) = O(nloglogn)</math>. | ||
| − | Finally, the array can be sorted in O(nloglogn). | + | Finally, the array can be sorted in <math>O(nloglogn)</math>. |
Latest revision as of 01:34, 28 April 2015
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) $.
