выполнения анализа следующего рекурсивного метода

Question

Может кто-то пожалуйста, помогите мне с анализом выполнения следующего кода:

public static void f(int n) 
{ 
    for (int i = 0; i <= n; i++) 
    { 
     System.out.print("+" + i); 
    } 
    if (n <= 1) 
    { 
     return; 
    } else 
    { 
     f(n/3); 
     f(n/3); 
    } 
} 

По мне, среда выполнения для рекурсивной формулы для кода:

Т (п) = сп + 2Т (п/3)

И я думаю, что ответ должен быть Θ(nlog(n)), но книжные решения показывают, что это будет Θ(n). Также в книге говорится, что для простоты предполагается n = 3^k.

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

Answer 1

Рассмотрите возможность использования Master Theorem. Ваша ситуация соответствует случаю 1, где f (n) = cn равно O (n). с a = 2 и b = 3, и применяя теорему, имеем T (n) велико. Theta (n^log3 (2)), которая является BigTheta (n).

Надеюсь, это поможет ...