Liczenie złożoności, a instrukcja warunkowa wenątrz pętli

Witam, potrzebuję wyliczyć złożoność dla następującego algorytmu:

for (i=0; i<=n-2;i++)
     for (j=i+1; j<=n-1;j++)
          if (A[j] % A[i] != 0)
         {
             for (k=0; k<=n-1;k++)
                printf (“hello”);
         }

Operacją elementarną jest wypisanie "hello".

Wygląda na to, że złożoność będzie wyliczona w taki sposób: (n-1)(n-1)n, czyli pesymistyczna wyniesie n^3,
ale ta instrukcja if mnie niepokoi, czy powinienem to jakoś uwzględnić w tworzeniu rozwiązania ?

Czy n^3 jest poprawnym rozwiązaniem ?

Pozdrawiam :)

No jeśli macierz A[n] zawiera na przykład liczby pierwsze (albo chociaż względnie pierwsze) to hello nigdy się nie wypisze, więc teoretycznie wpływa to na rozwiązanie...

Czyli mówiąc inaczej w przypadku optymistycznym a pesymistyczny .

Shalom napisał(a)

No jeśli macierz A[n] zawiera na przykład liczby pierwsze (albo chociaż względnie pierwsze) to hello nigdy się nie wypisze, więc teoretycznie wpływa to na rozwiązanie...

Ale zakładając, że mam podać złożoność pesymistyczną, to chyba mam prawo założyć że pętla for ze zmienną k w środku wykona się zawsze bo instrukcja warunkową if pozwoli jej na to i wtedy mój powyższy wzór na złożoność pesymistyczną jest poprawny, czy mam rację ?

Dzięki za odpowiedzi! Mam jeszcze 3 algorytmy i proszę o sprawdzenie czy dobrze rozumuję licząc rząd funkcji:

 
for (int i=1;i<=n;i++){
  int j=1;
  while (j<=i)
     j=j*2;
}

Pętla for wykona się n razy, a pętla while będzie wykonywana log_2(1) + log_2(2) + ... + log_2(n) razy, czyli moja złożoność wyniesie moim zdaniem n*logn

for (int i=1;i<=n;i*=2){
  int j=1;
  while (j<=i)
     j++;
}

Tutaj trochę sprawa się komplikuje, bo chciałoby się napisać log_2(n) [dla pętli for] * n(n+1)/2 [dla pętli while] i tak też zrobiłem za pierwszym razem, ale tutaj raczej będzie to trzeba rozwiązać w następujący sposób, bo dla...

(n=9)
dla i=1 pętla while wykona się 1 raz
dla i=2 pętla while wykona się 2 raz
dla i=4 pętla while wykona się 4 raz
dla i=8 pętla while wykona się 8 raz

Licząc w ten sposób mogę stwierdzić, że w przypadku pesymistycznym algorytm wykona 2n operacji aka. inkrementacja w pętli while będzie wykonana 2n razy.
Czy tak powinno być ?
Jeżeli TAK, to czy takie podchwytliwe operacje mają jedyne miejsce gdy w pierwszej pętli mamy do czynienia z ilością operacji wynoszącą logn ?

for (int i=1;i<=n;i*=2){
  int j=1;
  while (j<=n)
     j++;
}

Po poprzednim podchwytliwym dla mnie przykładzie tym razem także rozpisałem i ten sobie ze względu na podwajaną wartość dla i w zewnętrznej pętli i otrzymałem takie wyniki:

(dla n=10)
dla i=1 pętla while wykona się 10 razy
dla i=2 pętla while wykona się 10 razy
dla i=4 pętla while wykona się 10 razy
dla i=8 pętla while wykona się 10 razy
A więc łącznie wykona się n razy w każdym przebiegu, a przebiegów będzie log_2(n) a więc złożoność moim zdaniem wynosi n*logn, dobra ?

4. Jeszcze jedno pytanie ekstra. Rozwiązując zadania ze złożonością pesymistyczną i rzędem funkcji zauważyłem, że wyniki dla nich są identyczne, a więc czy można powiedzieć, że rząd funkcji = złożoność pesymistyczna, bo tak rozwiązywałem dotychczas te zadania, rozumowałem w taki sam sposób.