Wyliczanie złożoności dla algorytmu, gdzie pętla w pętli zależna od poprzedniej

Witajcie,
Potrzebuję pomocy w wyliczeniu złożoności dla algorytmów gdzie pętla wewnętrzna zależy od poprzednika tzn. zmiennej uzyskanej z poprzedniej pętli, przykładowo:

while (j<n)

Potrafię wyliczać złożoności dla z góry określonych zmiennych wzg. których porusza się pętla, ale nie wiem jak rozwiązać takie zadania jak poniżej.

m=0;
for (t=n-1; t>=0; t--)
 for (i=1; i<=n-t; i++)
 {
  j=0;
   while (j<n)
   {
    if (A[j]>A[j+1]) m=A[i]; 
    else if (A[j]<A[j+1]) m=A[j]; 
    else break;
    j++;
   }
 }

W założeniach mam podane, że rozmiar zadania wynosi n i operacja elementarna to porównania między elementami tablicy A.

Dla powyższego algorytmu muszę określić:

• przypadek pesymistyczny
• funkcję kosztu pesymistycznego
• rząd tej funkcji

Bardzo proszę o wytłumaczenie mi jak postępować w przypadku takich algorytmów.

Dziękuje i pozdrawiam serdecznie,
Jurek

to:

  j=0;
   while (j<n)
   {
    if (A[j]>A[j+1]) m=A[i]; 
    else if (A[j]<A[j+1]) m=A[j]; 
    else break;
    j++;
   }

jest to samo co to:

 for (int j=0; j<n; j++)
   {
    if (A[j]>A[j+1]) m=A[i]; 
    else if (A[j]<A[j+1]) m=A[j]; 
    else break;
   }

zakładając, że jeśli coś obliczasz w an operacjach to złożoność to O(n), możesz spokojnie powiedzieć, że wykonujesz tutaj w przybliżeniu:
nn*n/a operacji, gdzie a jest to jakaś stała większa od 1, zatem złożoność O(n^3), czyli prawdopodobnie cieńko

Dzięki za odpowiedź, ale muszę mieć takie rozwiązania rozwinięte, bo taka odpowiedź nie wystarczy dla prowadzącego zajęcia, niestety...

Jeżeli mamy te trzy pętle to w sumie najłatwiej powiedzieć, że n^3, bo to w sumie i tak pesymistyczny, ale ja muszę to wyliczyć i z tego co wiem to wylicza się to w jakiś dziwny sposób (nie wiem, szeregi?), tzn. potrzebuję sprowadzić to do postaci ze stałymi i innymi zmiennymi o niższych potęgach i dopiero wtedy wyciągnąć ewentualnie z wielomianu zmienną z największym stopniem potęgi.

Czy potrafi ktoś nakierować mnie jak wyliczać złożoność dokładnie, a nie na oko ? Dla mnie wystarczy na oko, ale na uczelni czepiają się niestety...

Dla t=n-1 wewnętrzna pętla for wykona się 1 raz,
...
dla t=0 wewnętrzna pętla for wykona się n razy.
Zatem wewnątrz pętla for wykona się 1+2+..+n = n*(n+1)/2 razy.
W pesymistycznym przypadku w pętli while nigdy nie nastąpi break i zawsze trzeba będzie wykonać 2 porównania =>
w pętli while będzie 2n porównań. W pesymistycznym przypadku wykonasz 2nn(n+1)/2=nn(n+1) porównań.