1) Use iteration method to solve the following recurrence T(n) =T(n-1) x n and T(1)=1.

2) Using substitution method, solve the following recurrence: T(n)=2*T(√n) +lgn.

3) Using Master Theorem, solve the following recurrence: T(n) = 3T(n/3) + O(lg n).

4) Using the recursion tree method, solve the following recurrence: T(n) = 3T(⌊n/4⌋) + Θ(n2).

**Subject Computer Science Data Structures and Algorithms**