CLRS 9.3 Selection in worst-case linear time | Rip's Infernal Majesty
In the algorithm SELECT, the input elements are divided into groups of 5. Will the algorithm work in linear time if they are divided into groups of 7? Argue that SELECT does not run in linear time if groups of 3 are used.
For groups of 7, the number of elements greater than x, or less than, is at least 2n/7 – 8, we have
T (n) ≤ T (n/7) + T (5n/7 + 8 ) + O(n)
This works in linear time as can be proved similar to case of group 5.
For groups of 3, the number of elements greater than x, or less than, is at least n/3 – 4, we have
T (n) ≤ T (n/4) + T (n/3 + 4) + O(n)
We can prove by induction this dose not work in linear time.
Read full article from CLRS 9.3 Selection in worst-case linear time | Rip's Infernal Majesty
No comments:
Post a Comment