Algorithm Given a positive integer q > 0, and real numbers s; u with 0 < s = 1. 1. (10p) Use the substitution method

Algorithm

Given a positive integer q > 0, and real numbers s; u with 0 < s <= u < 1, consider the function T given by T(0) = 0, and the recurrence T(n) = T(|sn|) + T(|un|) + n^(q) for n >= 1.

1. (10p) Use the substitution method to find a constraint on the values of q; s; u that makes it possible to find c > 0, expressed as a function of q and s and u, such that you can prove by induction in n that T(n) <= cn^(q) for all n >= 0

2. (5p) Let q = 2, s = 0:6, and u = 0:7. Use your result from part 1 to Find c such that T(n) <= cn^(2) holds for all n >= 0. For n from 1 to 10, tabulate T(n) and also cn^(2)

3. (5p) Finally, consider the case where s = u. With b =(1/s), the recurrence thus reads T(n) = 2 . T(|n/b|) + n^(q) Show that then the result you got in part 1 could have been predicted by the Master Theorem.