Guessing asymptotic upper bound by recursion tree. Verifying by substutution method and by Master Theorem

Question

My assignment is as follows: Find a guress for an asymptotic upper bound for the recurrence by using recursion trees. Verify the asymptotic upper bound by:

1: Substitution method
2: Master Theorem

T(n)= { Θ(1)               if n = 1
      { 3T(n/3) + Θ(n)     if n > 1

how do i approach this? I have some knowledge of recurrence trees, the substitution method and the Master Theorem. Please Help!

Answer 1

We have Case 2 of the Master theorem because

a = 3
b = 3
f(n) = n = Θ(n^log_3(3)) = Θ(n)

Therefore

T(n) = Θ(n*lg(n))

Of course

lg(n) = log_2(n).

Intuitively this means the cost of T is dominated neither by the cost of recursion nor by the work done in the recursion. This is the same as saying that in the recursion tree, the cost of the nodes at each level is asymptotically the same as the cost of leaves.

http://web.eecs.utk.edu/~parker/Courses/CS581-spring14/Lectures/3-Jan-16-Master-Mthd-Matrix-Mult-no-answers.pdf