Advanced algorithms design and analysis

Question 1 (15 POINTS): Usng asymptotic upper bound definition for "O", show that 20+1-0(2) Please show your work. Question 2. (20 POINTS): Given the recurrence: T(n) T(n- 1)+1 use substitution method to check whether T(n)-?(n). Please show your work. Question 3. (20 POINTS - 10 POINTS each) Gnen folowing recurences, use recursion tree method to determine the asymptotic bound or each recurrence. Please show your work .A) T(n)- T(n -1)+ n 3.B.) T(n)-2T (2) + n