Content deleted Content added
Tag: Reverted |
m Reverted edits by 136.232.6.66 (talk) (HG) (3.4.12) |
||
Line 189:
=== Best-case analysis ===
In the most balanced case, each time we perform a partition we divide the list into two nearly equal pieces. This means each recursive call processes a list of half the size. Consequently, we can make only {{math|log<sub>2</sub> ''n''}} nested calls before we reach a list of size 1. This means that the depth of the [[Call stack|call tree]] is {{math|log<sub>2</sub> ''n''}}. But no two calls at the same level of the call tree process the same part of the original list; thus, each level of calls needs only {{math|''O''(''n'')}} time all together (each call has some constant overhead, but since there are only {{math|''O''(''n'')}} calls at each level, this is subsumed in the {{math|''O''(''n'')}} factor).
=== Average-case analysis ===
| |||