Difference between revisions of "TADM2E 4.24"
From Algorithm Wiki
(Recovering wiki) |
|||
| (One intermediate revision by the same user not shown) | |||
| Line 1: | Line 1: | ||
It's not clear to me if the first <math>n - \sqrt n</math> element being sorted means that the remaining <math>\sqrt n</math> elements are all bigger or not, but let's suppose they are not, since that's more general. | It's not clear to me if the first <math>n - \sqrt n</math> element being sorted means that the remaining <math>\sqrt n</math> elements are all bigger or not, but let's suppose they are not, since that's more general. | ||
| − | First sort the remaining <math>\sqrt n</math> elements in <math>O(\sqrt n \log n)</math> time. After that we can do a simple merge step to merge the two sorted arrays in <math>O(n)</math> time. Since <math>\sqrt n</math> dominates <math>\log n</math> we can come to the conclusion that the total running time of this algorithm is: <math>O(\sqrt n \log n + n) = O(\sqrt n \sqrt n + n) = O(n + n) = O(n)</math> | + | First sort the remaining <math>\sqrt n</math> elements in <math>O(\sqrt n \log \sqrt n)</math> time. After that we can do a simple merge step to merge the two sorted arrays in <math>O(n)</math> time. Since <math>\sqrt n</math> dominates <math>\log \sqrt n</math> we can come to the conclusion that the total running time of this algorithm is: <math>O(\sqrt n \log \sqrt n + n) = O(\sqrt n \sqrt n + n) = O(n + n) = O(n)</math> |
Latest revision as of 14:35, 1 February 2015
It's not clear to me if the first $ n - \sqrt n $ element being sorted means that the remaining $ \sqrt n $ elements are all bigger or not, but let's suppose they are not, since that's more general.
First sort the remaining $ \sqrt n $ elements in $ O(\sqrt n \log \sqrt n) $ time. After that we can do a simple merge step to merge the two sorted arrays in $ O(n) $ time. Since $ \sqrt n $ dominates $ \log \sqrt n $ we can come to the conclusion that the total running time of this algorithm is: $ O(\sqrt n \log \sqrt n + n) = O(\sqrt n \sqrt n + n) = O(n + n) = O(n) $
