再発関数の実行時

Question

int foo(int n) 
{ 
    if(n==0) 
     return 1; 
    int sum = 0; 
    for(int i = 0;i < n;i++) 
     sum += foo(n-1); 
    return sum; 
} 

私は最近、ランダウの記号を学んでいます。 は、誰かが私にビッグO記法を使って、どのようにこの関数の実行時間を提示することによって、この再発関数の実行時間を決定する方法についてのアイデアを与えることができます。

Answer 1

だからあなたは大きなnのFOO（n）を実行するとどうなるかを考えます。合計は、foo（n-1）への呼び出しのn倍で構成されます。再帰ツリーの次のレベルでは、FOO（n-1）の持っているし、再び我々は、nを呼び出す（-1）倍のfoo（N-1-1）が、n個のfoo（N-1）のそれぞれについて、私達の木の枝。私たちはfoo（n-n）まで行く必要があるので、ツリーの高さはnであることがわかります。したがって、すべての再帰ステップで、fooの1つのインスタンスをfoo（n-1）のO（n）インスタンスに変換します。

私はそれが運動のように思えるが、明らかに終了しそうです、ただ再帰ツリーのいくつかのレベルを描き、あなたのあなたの答えを見つけるように私は答えを明らかにする必要がある場合は、特定のはないです。