4.35

From The Algorithm Design Manual Solution Wiki
Revision as of 18:30, 20 September 2020 by Algowikiadmin (talk | contribs) (Created page with "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...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

It's not clear to me if the first [math]\displaystyle{ n - \sqrt n }[/math] element being sorted means that the remaining [math]\displaystyle{ \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]\displaystyle{ \sqrt n }[/math] elements in [math]\displaystyle{ 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]\displaystyle{ O(n) }[/math] time. Since [math]\displaystyle{ \sqrt n }[/math] dominates [math]\displaystyle{ \log \sqrt n }[/math] we can come to the conclusion that the total running time of this algorithm is: [math]\displaystyle{ O(\sqrt n \log \sqrt n + n) = O(\sqrt n \sqrt n + n) = O(n + n) = O(n) }[/math]


Back to Chapter 4