1. (20 points) Solving Recurrences (I). Consider the following recurrence: T(n)=T(n1)+10 (a) Assume that the base case is T(1)=(1). Show that the solution to this recurrence is O(n) using: (a) (8 points) The substitution method (the starting guess is T(n)=O(n) ) (b) ( 8 points) The recursion tree method (b) (2 points) Is T(n)=(n) ? Explain your answer. (c) (2 points) Solve the recurrence using the Master Theorem, if possible