algorithm - 渐近上限

Question

您好，我用递归树方法解决了一个问题。然后我得出了下面的方程式。
n
∑ 3^(i-1)(n - (i - 1))
i=1

我需要找到该方程的渐近上限。任何帮助，将不胜感激。

Answer 1

Wolfram Alpha 是一个很好的工具:https://www.wolframalpha.com/input/?i=sum(3%5E(i-1)(n+-+i+%2B+1)+for+i+%3D+1..n)

该工具将总和简化为:(-2n + 3^(n+1) - 3)/4。

就大 O 而言，即 O(3^n)。