algorithm - Average Runtime of Quickselect - Stack Overflow
In quickselect, as specified, we apply recursion on only one half of the partition.
Average Case Analysis:
First Step: T(n) = cn + T(n/2)
where, cn = time to perform partition, where c is any constant(doesn't matter).
T(n/2) = applying recursion on one half of the partition.
Since it's an average case we assume that the partition was the median.
As we keep on doing recursion, we get the following set of equation:
T(n/2) = cn/2 + T(n/4)
T(n/4) = cn/2 + T(n/8)
.
.
.
T(2) = c.2 + T(1)
T(1) = c.1 + ...
Summing the equations and cross-cancelling like values produces a linear result.
c(n + n/2 + n/4 + ... + 2 + 1) = c(2n) //sum of a GP
Hence, it's O(n)
Read full article from algorithm - Average Runtime of Quickselect - Stack Overflow
No comments:
Post a Comment