[Algorytmy] Złożoność obliczeniowa

Mam napisać, jaka jest złożoność obliczeniowa tego fragmentu:

for i <-- 1 to n

     do for j <-- 1 to i

          do for k <-- 1 to i

                   do x <-- x+1

Problem w tym, że nie wiem, jak obliczyć złożoność obliczeniową.

Są trzy pętle, ten kod rozumiem, że:

pierwszy element ma indeks i, j oraz k, jeśli wykonamy znów ponownie, wtedy drugi element ma indeks i, j oraz k, i tak dalej do n.

Jeżeli są 3 pętle for to mamy do czynienia z z algorytmem O(n^3).

jest tak dlatego,że każdej następnej danej ilość operacji wzrasta 3 krotnie

O(1)=1

O(1,2)=8 2*2*2

O(1,2,3)=27 3*3*3

O(1,2,3,4)=4*4*4=64

Patrząc na dwie wewnętrzne pętli, instrukcja x <-- x+1 wykona się i^2 razy. To wszystko natomiast zostanie wykonane n razy dla i od 1 do n. Czyli piękny wzorek z pomocą Wolfram|Alpha: http://www.wolframalpha.com/input/?i=sum+i%3D1…n++i**2

Dziękuję, a funkcja zmienna n wynosi n^3?

A gdyby było tak:

for i <-- 1 to n

     do for j <-- 1 to i

          do for k <-- 1 to j

                   do x <-- x+1

Zmieniło się tylko w trzeciej pętli od 1 do j. To jaką funkcję zmiennej n ma?

Nadal to O(n^3), owszem nieco mniejsze współczynniki tej O()