Problem 2. (20 marks) Find asymptotic upper and lower bounds for each of the following recurrences. Unless specified otherwise, assume that in each case T(1)1 (or any small constant). Make your bounds as tight as you can a. (3 marks) Tn) ST()+n b" (3 marks) T(n) = 2T(3) + 2n log n c. (3 marks) T(n)=3T(H) +log2 n d. (3 marks) T(n)=ng+Vn) + V3024 e. (4 marks) T(n)-T(n-1) f. (4 marks) T(n) = T(n-1) + T(n-2) + 1 with base case of T(1) = 1 and T(2) = 2