java - 次の再帰メソッドのランタイム分析

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);
    }
}

私によると、コードの再帰式の実行時間は次のとおりです。

T(n) = cn + 2T(n/3)

そして、答えは であるべきだと思いますΘ(nlog(n))が、本の解決策はそれが であることを示していますΘ(n)。n = 3^kまた、この本は、簡単にするために仮定するように言っています。

誰かが私に正しい答えを説明してもらえますか?