求解递归定义的函数

Question

找出递归定义的函数 T(n) = T(n-1) + 3 的 运行 时间复杂度。我完全不知道该怎么做。

Answer 1

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

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