<tex> T(0) = 0 </tex>

<tex> T(i) \le \frac {T(i + 1) + T(i - 1)}{2} + 1 </tex> pentru $0 < i < N$ ({$N$} e numărul de variabile booleene ale expresiei)

<tex> T(i) \le \dfrac {T(i + 1) + T(i - 1)}{2} + 1 </tex> pentru $0 < i < N$ ({$N$} e numărul de variabile booleene ale expresiei)

Se pune semnul de inegalitate pentru că ambele variabile pot avea valori diferite faţă de cele din soluţie, deci schimbarea valorii oricăreia ar putea să ne aducă mai aproape de soluţie.

Ne interesează numai limitele superioare, deci folosim doar egalităţi în loc de inegalităţi:

<tex> X(0) = 0 </tex>, <tex> X(i) = \frac {X(i + 1) + X(i - 1)}{2} + 1 </tex>, <tex> X(N) = X(N - 1) + 1 </tex>

<tex> X(0) = 0 </tex>, <tex> X(i) = \dfrac {X(i + 1) + X(i - 1)}{2} + 1 </tex>, <tex> X(N) = X(N - 1) + 1 </tex>

Dacă adunăm toate ecuaţiile obţinem:

<tex> X(0) + X(1) + ... + X(N) = </tex> <tex> \frac {X(0) + X(1) + 2X(2) + ... + 2X(N - 2) + X(N - 1) + X(N)}{2} + X(N) + N - 1 </tex>

<tex> X(0) + X(1) + ... + X(N) = </tex> <tex> \dfrac {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> \frac {X(1) + X(N - 1) - X(N)}{2} = N - 1 </tex>, iar din <tex> X(N) = X(N - 1) + 1 </tex> rezultă că <tex> X(1) = 2N - 1 </tex>. Mai departe avem că <tex> X(2) = 4N - 4 </tex> <tex> ... </tex> <tex> 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> \dfrac {X(1) + X(N - 1) - X(N)}{2} = N - 1 </tex>, iar din <tex> X(N) = X(N - 1) + 1 </tex> rezultă că <tex> X(1) = 2N - 1 </tex>. Mai departe avem că <tex> X(2) = 4N - 4 </tex> <tex> ... </tex> <tex> X(i) = 2iN - i^2 </tex>, de unde, când <tex> i = N </tex>, avem că <tex> X(N) = N^2 </tex>.

Astfel, numărul mediu de paşi ai algoritmului este pătratic în numărul $N$ de variabile. Lăsând algoritmul să ruleze de 2-3 ori mai mulţi paşi decât numărul mediu, avem o probabilitate foarte mare să ajungem la rezultat.