什麼決定了遞歸關係中的常量？

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) 

希望它清除的東西。