Каково асимптотическое время выполнения

Question

Может кто-нибудь помочь мне проверить правильность и объяснить, почему

What is the asymptotic running time of T(n) = 3T(n/3) + O(n) with T(1) = 1   _______ .  

Мой ответ n ^{log ₃ 3} .

Answer 1

Вы, кажется, неправильно применили Основную теорему .

Мы имеем T (n) = a T (n / b) + O (n) , где a, b = 3 .

Поскольку здесь функция повторения равна O (n) , она принимает вид O (n ^{c *).1015 * log k (n))} с c = 1 и k = 0 .

Таким образом, мы находимся в случаегде c = log _a (b) = 1 .

Тогда согласно основной теореме сложность составляет O (n ^c log ^{k + 1} (n)) , то есть O (n log (n)) .