https://algorist.com//algowiki/index.php?title=4.35&feed=atom&action=history4.35 - Revision history2024-03-29T06:09:06ZRevision history for this page on the wikiMediaWiki 1.34.2https://algorist.com//algowiki/index.php?title=4.35&diff=322&oldid=prevAlgowikiadmin: 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..."2020-09-20T18:30:31Z<p>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..."</p>
<p><b>New page</b></p><div>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.<br />
<br />
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><br />
<br />
<br />
Back to [[Chapter 4]]</div>Algowikiadmin