Given the following recurrences. Use the recursion tree method to solve each of them. Represent the runtime in one of the asymptotic notations properly. Show your work of the solving process.

1)

T(n) = O(1) for n = 1, 2

T(n) = 3T(n/3) + O(n) for n > 2 (assume n is an exact power of 3)

2)

T(n) = O(1) for n = 1, 2

T(n) = 3T(n/3) + O(1) for n > 2 (assume n is an exact power o f3)