4) [3] State an asymptotic upper bound using O-notation for the following time function (use Linear Master Theorem). 1. T(n) = T(n-1000) + n 2. T(n) = 3T(n-2) +n 3. T(n) = 1/2T(n-1) + 1 5) [4] Consider a recursion tree that looks like this: n W (n/3) (n/3) (n/3) (n/9) (n/9) (n/9) (n/9) (n/9) (n/9) (n/9) (n/9) (n/9) 1. What recurrence relation could generate this recursion tree? 2. How many levels would there be in this tree, as a function of n? 3. How many leaves would be in this tree, as a function of n? 4. Solve the recurrence to obtain an asymptotic expression for T(n) as a function of n