Как решить следующие повторения и найти привязку к тэте

Question

1. T (n) = T (n-1) + n ^ c
2. T (n) = T (n-1) + c ^ n

где с постоянная

Answer 1

Если вы развернете рекурсию, для первого случая вы получите:

1^c + 2^c + ... + (n-1)^c + n^c

которая является формулой Фолхабера. Он говорит вам, что сложность O(n^(c+1))

Второй:

c^1 + c^2 + ... + c^(n-1) + c^n

которая является суммой геометрических и O(c^n)