为给定函数写循环

Question

我正在尝试为以下函数的运行时间编写递归关系：

function G(n):
    if n>0 then:
        x=0
        for i = 1 to n:
            x = x + 1
         G(n-1)
    end if

我想到的是：

 T(n) = 1 if n <= 0
 T(n) = T(n-1) + 1 if n>0

但是我被告知这是不正确的，我不知道为什么或正确的解决方案是什么。非常感谢任何帮助！

Answer 1

T(n) = 1 if n <= 0
T(n) = T(n-1) + O(n) if n>0

而不是O(1)，应该是O(n)，因为你是从1循环到n

如果解决递归，整体复杂度为O(n²)

Write Recurrence for Given Function