Угадывание асимптотической верхней границы рекурсивным деревом. Проверка методом замещения и с помощью мастер-теоремы

Question

Мое назначение выглядит следующим образом: Найдите усиление асимптотической верхней границы для повторения с использованием деревьев рекурсии. Проверьте асимптотическую верхнюю границу:

1: Substitution method 
2: Master Theorem 

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

Как подойти к этому? У меня есть знание деревьев повторения, метод подстановки и Мастер-теорема. Пожалуйста помоги!

Answer 1

Мы имеем случай 2 теоремы Мастера, потому что

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

Поэтому

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

Конечно

lg(n) = log_2(n). 

Наглядно это не означает, что стоимость Т доминирует ни по стоимости рекурсии или работы, выполненной в рекурсии. Это то же самое, что сказать, что в дереве рекурсии стоимость узлов на каждом уровне асимптотически такая же, как и стоимость листьев.

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