反復関係で定数を決めるのは何ですか？

Question

は、私は次のアルゴリズムを持っていると言う：

ArraySum (A, n) 
    if n = 1 
     return A[0] 
    return A[n-1] + ArraySum(A, n-1) 

だから、漸化式が

 | c1   n = 1 
T(n) = | 
     | T(n-1) + c2 n > 1 

になり、私はc1 = 0とc2 = 3としていくつかの材料を見ましたが、どのように私はc1とc2を決定については行くのですか？

Answer 1

時間の複雑さについて話している限り、c1とc2の両方はnとは無関係に一定です。彼らはO（1）です。だから、

 | O(1)   n = 1 
T(n) = | 
     | T(n-1) + O(1) n > 1 

そして解決に

。

T(n) = O(n) 

希望のものをクリアします。