Q 1. Recursive Equations (25%) Solve the following recurrence equations and give a e bound in terms of n for each of them. (1) T(n) = T(n 2)+1; 10) = 0; x is even and r 0. [5%) (2) T(n) = T(n-1) + 2n; T(0) = 0; n > 0. [5%] (3) T(n) = 4T() +1; T(1) = 0; n > 1 (You may assume that n=2" and m is a natural number) [5%] (4) T(n) = 4T() +n; T(1) = 0. (You may assume that n=4m where m is a natural number) [5%] (5) T(n) { $(x) +2 153 (You may assume that n = 3*" where m is a natural number) [57]