以下表达式的净运行时间是多少？

Question

对于递归算法，我想出了以下表达式来计算运行时间。但我不清楚如何简化此操作，并用Big-O表示法表示。

如果只是4k，然后我知道这是一个简单的GP系列，我们可以采取的最后一项是4n作为运行时间的最坏情况。帮助我了解如何在这里处理(k+1)。

Answer 1

只是尽量简化用语有点

 
Σk=0,...,n 4k(k+1) < Σk=0,...,n 4k(n+1) = (n+1) Σk=0,...,n 4k 

所以这是O(n⋅4n)。由于4n(n+1)是总和的一部分，所以这个界限很紧。

注意：“运行时间”的含义通常称为“复杂性”。