[Teoria złożoności] Rząd funkcji T(N) od liczby mnożeń.

[LawlietDB]

Dzień dobry

Nie bardzo wiem w jaki sposób wyznaczyć ten rząd funkcji dlatego też proszę o pomoc. Oto treść zadania:

Jaki jest rząd funkcji \(\displaystyle{ T(N)}\) gdzie \(\displaystyle{ T(N) =}\) liczba mnożeń wykonanych przez poniższy program zakładając, że początkową wartością zmiennej \(\displaystyle{ n}\) typu integer jest równa \(\displaystyle{ N}\)?

Kod: Zaznacz cały

res: = 1;
while( n > 0) do {
   i:=0;
   while(i < n) { 
      res:= res+i*n; 
      i:=i*2;
   };
   n:= n-1;
}

\(\displaystyle{ T(N) = \Theta(\ldots)}\)?

Z góry dziękuję za pomoc.

[bartek118]

Zewnętrzna pętla wykona się \(\displaystyle{ N}\) razy, wewnętrzna niestety działa w nieskończoność, więc \(\displaystyle{ T(N) = \infty}\).

[LawlietDB]

Dziękuję za odpowiedź

Zrozumiałem