TADM2E 4.24

From Algorithm Wiki
Revision as of 14:33, 1 February 2015 by Far9999 (Talk | contribs)

Jump to: navigation, search

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 n $ we can come to the conclusion that the total running time of this algorithm is: $ O(\sqrt n \log n + n) = O(\sqrt n \sqrt n + n) = O(n + n) = O(n) $