Content deleted Content added
Added a note about my changes to the analysis of running-time. |
m Signing comment by Patmorin - "Added a note about my changes to the analysis of running-time." |
||
Line 35:
== Analysis ==
I just corrected the analysis section. The recurrence <math>T(n)=2T(n/2)+ O(n)</math> doesn't describe the average the running time of the algorithm under any reasonable interpretation of average-case. That particular recurrence does resolve to <math>\Theta(n\log n)</math> and the expected running-time of the algorithm is <math>\Theta(n\log n)</math> under some interpretations of average-case, though. <!-- Template:Unsigned --><small class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Patmorin|Patmorin]] ([[User talk:Patmorin#top|talk]] • [[Special:Contributions/Patmorin|contribs]]) 19:07, 10 December 2019 (UTC)</small> <!--Autosigned by SineBot-->
| |||