Content deleted Content added
Developing recursion in the cost bound doesn't provide a real proof per se. |
|||
Line 147:
The O(''n'') term ''c n'' is for the partitioning work (we visited each element a constant number of times, in order to form them into n/5 groups and take each median in O(1) time).
From this, using induction, one can easily show that
:<math>T(n) \leq 10 \cdot c \cdot n \in O(n).</math>
=== Important notes ===
| |||