Aşağıdaki ifadenin net çalışma süresi nedir?

Question

Yinelemeli bir algoritma için, çalışma süresini hesaplamak üzere aşağıdaki ifadeyle geldim. Ama bunu basitleştirmek ve Big-O notasyonunda ifade etmek için açık değilim.

sadece 4k, o zaman sadece bir GP serisi olduğunu biliyoruz ve çalışma süresi en kötü durumda olarak 4n olan son dönem alabilir ise. (k+1) ile nasıl başa çıkılacağını anlatayım.

Answer 1

Sadece terimin

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

Yani bu O(n⋅4n) olduğunu biraz basitleştirmek deneyin. Ve bu bağ sıkıdır, çünkü 4n(n+1) toplamın bir parçasıdır.

Uyarı: "çalışma süresi" ile kastedilen, genellikle "karmaşıklık" olarak adlandırılır.