以下の式の実行時間はどれくらいですか？

Question

再帰アルゴリズムでは、次の式を使って実行時間を計算しました。しかし、これを簡略化する方法については明確ではなく、Big-O表記で表現しています。

それだけ4kであれば、私はそれが単にGPシリーズであることを知っていると我々は時間を実行している最悪のケースとして4nで最後の項を取ることができます。 (k+1)の対処方法を教えてください。

Answer 1

だけので、これはO(n⋅4n)である用語を少し

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

を簡素化してみてください。 4n(n+1)が合計の一部であるため、この境界は厳しいです。

注意：「実行時間」とは、通常「複雑さ」と呼ばれます。