TADM2E 4.24

From Algorithm Wiki
Revision as of 18:13, 11 September 2014 by Algowikiadmin (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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>