Złożoność obliczeniowa

[adaksik]

Potrzebuję pomocy w zadaniu związanym z obliczaniem złożoności obliczeniowej. Dla Was to pewnie fala sekund więc baaaardzo dziękuję z góry za pomoc.

a)Oblicz złożoność obliczeniową w ogólnym przypadku i złożoność pesymistyczną dla podanego poniżej algorytmu.
b)Wykonaj poniższy algorytm dla zbioru liczb: 7,1,5,2,2,6,1.

Algorytm (tablica T, rozmiar_tablicy N) {
for(j=2; j<N; j++) {
x=T[j];
i=j-1;
while (i>0 && T<=x) {
T[i+1]=T;
i=i-1;
}
}

[Laurearel]

a) patrz, bierzesz jeden z wierszy "najgłębiej" programu (tj np. T = T[i+1]) i sprawdzasz ile razy się wykona. Z tego wyniku znajdujemy złożoność, czyli będzie to O(n^{2}) (złożoność pesymistyczna)

b) no to wykonaj , w czym problem ? ;p