<tex> X(0) + X(1) + ... + X(N) </tex> <tex> = (X(0) + X(1) + 2X(2) + ... + 2X(N - 2) + X(N - 1) + X(N))/2 + X(N) + N-1 </tex>

De aici avem că <tex> (X(1) + X(N) - X(N - 1)) / 2 = N </tex>, din <tex> X(N) = X(N - 1) + 1 </tex> avem <tex> X(1) = 2N - 1 </tex>. Mai departe avem că <tex> X(2) = 4n - 4 ... X(i) = 2iN - i^2^ </tex> de unde, când <tex> i = N </tex> avem că <tex> X(N) = N^2^ </tex>.

De aici avem că <tex> (X(1) + X(N - 1) - X(N)) / 2 = N - 1 </tex>, din <tex> X(N) = X(N - 1) + 1 </tex> avem <tex> X(1) = 2N - 1 </tex>. Mai departe avem că <tex> X(2) = 4n - 2 ... X(i) = 2iN - i </tex> de unde, când <tex> i = N </tex> avem că <tex> X(N) = 2N^2 - N </tex>.

Astfel, numărul mediu de paşi ai algoritmului este $N^2^$ iar dacă aplicăm algoritmul în mod aleator de mai multe ori avem o probabilitate foarte mare să ajungem la rezultat.

Astfel, numărul mediu de paşi ai algoritmului este $2N^2^ - N$ iar dacă aplicăm algoritmul în mod aleator de mai multe ori avem o probabilitate foarte mare să ajungem la rezultat.

h3(#solutie4). Soluţie $O(M + N)$