Master Method - Recurrence relation with two Ts

Question

I am taking a data structures and algorithms course (which has been tough). We learned about the master method to solve basic recurrence relations when they are in the form aT(n/b)+f(n). Now we have learned about the linear time selection algorithm which has a relation that is not in this form and I am being asked to find its worse case running time is asymptotic notation.

I have found the the recurrence relation as:

It seems to me that the Master Method does not account for this - I may very well be wrong. If it doesn't, then how do you find the worse case running time?

Answer 1

The master theorem doesn't apply, but it's not too hard to prove a tight bound for this recurrence directly.

You know you can't do better than O(n), because that term is already in the recurrence. You have been told that it's a linear time algorithm and with some experience you would guess that from the fact that the total size of the subproblems is smaller than n by some factor, so it is a good bet that you can do O(n).

What remains is to prove it.

You can prove this pretty easily by induction. Let C be a (large) constant such that:

T(n) <= T(n/101 + 1) + T(151n/202 + 101) + C(n+1)/202, for all n, (eq 1), and

T(n) <= C(n+1), for all n < 1000 (eq 2)

For any n >= 1000, if (eq 2) holds for all smaller n, then we have

T(n) <= T(n/101 + 1) + T(151n/202 + 101) + C(n+1)/202 (eq 1)

T(n) <= C(n+202)/101 + C(151n+20604)/202 + C(n+1)/202 (subst eq 2)

T(n) <= C(2n+404)/202 + C(151n+20604)/202 + C(n+1)/202

T(n) <= C(156n+20604)/202

T(n) <= C(0.78n + 102) <= C(n - 0.22n + 102) <= C(n - 220 + 102) (because n>=1000)

T(n) <= C(n+1)

So, if we choose C as above, then the fact that (eq 2) holds for n < 1000 implies that it holds for all n, and T(n) is in O(n)