Difference between pages "1.31" and "4.35"
(Created page with "Back to Chapter 1.") |
(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...") |
||
| Line 1: | Line 1: | ||
| − | Back to [[Chapter | + | 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 \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> | ||
| + | |||
| + | |||
| + | Back to [[Chapter 4]] | ||
Latest revision as of 18:30, 20 September 2020
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
