1. Solve the following:

For each of the following recurrences, give an expression for the running time T(n) if the recurrence can be solved using the Master Theorem. Otherwise, indicate that the Master theorem does not apply.

a) T(n) = 2T() + O(n),

b) T(n) = 9T(n/3) + O(n³),

c) T(n) = 3T(n/9) + 5,

d) T(n) = 5T(n/2) + 2n²,

e) T(n) = 8T(n/2) +O(n³).

f) How many times does the following program print still going? Express your answer as a function of n (in O(.) form).

function f(n)

if n > 1:

for i=0 to n-1:

print_line(still going)

f(n/3)

f(n/3)

Hint: Let T(n) be the number of times that the function f(n) will print "still going". You need to write a recurrence for T(n) and solve it (using any method you like). You may assume n is a power of 3.