recursion - 求解递归定义的函数

Question

找到递归定义的函数 T(n) = T(n-1) + 3 的运行时复杂度。我完全不知道如何做到这一点。

标签： recursionruntimecomplexity-theory

Answer 1

在这种类型的递归中，您可以应用集合定理：https ://www.eecis.udel.edu/~saunders/notes/recurrence-relations.pdf

在您的情况下，b = a = 1 和 d = 0，因此复杂度为 O(n)。