For the following recurrences, solve them in O( ) notation (best possible). Where appropriate, you need to express your answer as a polynomial, in other words in the form n^c for a constant c. For example, if you have a solution in the form such as 7^{log_{3}n} then you need to re-express it as n^c. If you have a solution such as O(n^{log_{5}2}) then that's OK. You need to show your work for solving the recurrence. You can use the Master Theorem to check your work, but I will downvote if you just apply it without showing work for solving the recurrence.

1. T(n)=2T(n/3)+1

2. T(n)=5T(n/4)+10n

3. T(n)=9T(n/3)+n2