Content deleted Content added
Unpicked6291 (talk | contribs) m Add warning about "we" |
m Dating maintenance tags: {{Inappropriate person}} |
||
Line 213:
== Formal analysis ==
{{inappropriate person|section|we|excessively|date=April 2025}}
=== Worst-case analysis ===
The most unbalanced partition occurs when one of the sublists returned by the partitioning routine is of size {{math|''n'' − 1}}.<ref name="unbalanced">The other one may either have {{math|1}} element or be empty (have {{math|0}} elements), depending on whether the pivot is included in one of subpartitions, as in the Hoare's partitioning routine, or is excluded from both of them, like in the Lomuto's routine.</ref> This may occur if the pivot happens to be the smallest or largest element in the list, or in some implementations (e.g., the Lomuto partition scheme as described above) when all the elements are equal.
| |||