以下表達式的淨運行時間是多少？

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)是總和的一部分，所以這個界限很緊。

注意：「運行時間」的含義通常稱爲「複雜性」。