Termin zajęć: 29/30.03.2011
Do przygotowania:
Zajęcia odbywać się będą głownie przy tablicy. Nie ma konieczności przynoszenia laptopów.
Umożliwia szybkie wyznaczanie rozwiązania równania rekurencyjnego postaci:
gdzie:
Wtedy T(n) może być ograniczona asymptotycznie w następujący sposób:
Metoda graficzna:
for(i=0;i<n;i++) for(j=0;j<n;j++) OD
for(i=0;i<n;i++) for(j=0;j<n;j+=2) OD
for(i=0;i<n;i+=2) for(j=0;j<i;j++) OD
for(i=0;i<n;i+=2) for(j=i;j>=1;j/=2) OD