In Quickselect, T(n)<=T(n/5)+T(7n/10)+cn, prove that T(n) = O(n)

+1 vote
asked Feb 7 in D&C by Hao Wen (196 points)

1 Answer

+1 vote
Assume that T(n) <= 10cn, where c is a constant.

Prove it by induction:

First, there is T(1) = O(1), satisfying that T(1) <= 10cn.

Assume that T(m)<=10cm for all m <= n-1

thus, for n, we have T(n) <= T(n/5) + T(7n/10) + cn

since n/5 <= n-1, 7n/10 <= n-1

For n, there is:

T(n) <= 10c * n/5 + 10c * 7n/10 + cn = 2cn + 7cn + cn = 10cn

Thus, T(n) <= 10cn for all n's. So that T(n) = O(n)
answered Feb 7 by Hao Wen (196 points)
I think it is hard to guess if u change the cn to square(n)
The Book: Analysis and Design of Algorithms | Presentations on Slideshare | Lecture Notes, etc
...