Kod: Zaznacz cały
1: for i = 1 to n do
2: j = i
3: while j < n do
4: sum = P(i; j)
5: j + +
6: end while
7: end for
1) Gdy \(\displaystyle{ P(i;j)}\) kosztuje nas \(\displaystyle{ 1}\)
2) Oraz gdy kosztuje nas \(\displaystyle{ j}\)
1) Bardzo łatwo można zauważyć, że będzie to złożenie \(\displaystyle{ \Theta (n \cdot n)=\Theta(n^2)}\)
2)Zauważmy, że nasza \(\displaystyle{ sum=j}\)
Zatem skoro zewnętrzna wykona się \(\displaystyle{ n}\) razy wewnętrzny while wykona się \(\displaystyle{ n^2}\) ponieważ będziemy mieć \(\displaystyle{ n}\) sum zatem złożoność tutaj będzie wynosić \(\displaystyle{ \Theta (n^2 \cdot n) = \Theta (n^3)}\)
Proszę ocenić tok mojego rozumowania.