Question

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

Answer 1

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)