runtime - この再帰関数の大きなシータ実行時間

Question

この関数の Big-Theta の実行時間を把握するのに少し助けが必要です。

int recursive(int n) {

    sum = 0;
    for (int i = 1; i <= n; i++)
        sum++
    if (n > 1)
        return sum + recursive(n-1);
    else
        return n;
}

for ループが関数内にない場合、この関数の実行時間がどのようになるかはわかっていますが、ループが原因で少し気分が落ち込んでいます。何かアドバイス？

Answer 1

• 再帰的ではなく単なるforループである場合、関数は になりますO(n)。
• 再帰的で、forループがなければ、 O(n).
• しかし、それはn再帰的なステップを実行しており (これは であることがわかっていますO(n)) 、各ステップでO(n) forループがありnます。

それで...それは役に立ちますか？