* A > B -> R ~i~ > R ~j~ -> se elimina R ~i~
* A = B -> se elimina R ~j~ (se presupune ca R ~i~ < R ~j~ )

Este evident ca in primele doua cazuri decizia de eliminare este corecta. Daca A = B , iar decizia luata de eliminare a fost gresita, anume R ~i~ > R ~j~, cum R ~i~ = ABC = AAC si R ~j~ = BCA = ACA, inseamna ca A > C (daca A ar fi fost egal cu C atunci R ~i~ = R ~j~, si nu ar mai fi contat ce element se elimina), deci elementul pastrat va fi oricum eliminat de rotatia R ~2j-i~ = CAA sau de o alta rotatie care s-a dovedit a fi mai mica decat CAA la pasii anteriori. La a i-a parcurgere a listei, distanta intre doua rotatii aflate pe pozitii consecutive in lista este maxim 2^(i-1)^, iar in lista sunt cel mult [ n / 2^(i-1)^ ] elemente, astfel facandu-se O(N) comparatii. In acest mod obtinem un algoritm corect de complexitate O(N * log N).

Este evident ca in primele doua cazuri decizia de eliminare este corecta. Daca A = B , iar decizia luata de eliminare a fost gresita, anume R ~i~ > R ~j~, cum R ~i~ = ABC = AAC si R ~j~ = BCA = ACA, inseamna ca A > C (daca A ar fi fost egal cu C atunci R ~i~ = R ~j~, si nu ar mai fi contat ce element se elimina), deci elementul pastrat va fi oricum eliminat de rotatia R ~2j-i~ = CAA sau de o alta rotatie care s-a dovedit a fi mai mica decat CAA la pasii anteriori. La a i-a parcurgere a listei, distanta intre doua rotatii aflate pe pozitii consecutive in lista este maxim 2^(i-1)^, iar in lista sunt cel mult [ n / 2^(i-1)^ ] elemente, astfel facandu-se O(N) comparatii. In acest mod obtinem un algoritm corect de complexitate O(N * log N).
 
==code(c) |
L <- {0,1,2,…,N-1};
cat timp |L|>1 executa
    pentru k <- 1, |L|-1, +2 executa
    i <- L[k]; j <- L[k+1];
    A <- S[i..j-1]; B <- S[j..2j-i-1];
    daca A <= B atunci elimina L[k+1];
        altfel elimina L[k];
    sfarsit pentru
sfarsit cat timp
scrie L[1]
==