Relacja mniejszości dla ciągów niech będzie relacją mniejszości leksykograficznej.
Rotacją ciągu u=u[1..n] jest każdy ciąg postaci u(k) = u[k+1..n]u[1..k]. (W szczególności u(0)=u(n)=u).
Zdefiniujmy:
D(u)={k:1≤k≤n oraz u(k)>w(j) dla pewnego j},
D(w)={k:1≤k≤n oraz w(k)>u(j) dla pewnego j}.
Skorzystamy z prostego faktu:
Jeśli D(u)=[1..n] lub D(w)=[1..n], to u,w nie są równoważne. Poprawność algorytmu wynika teraz z tego, że po każdej głównej iteracji zachodzi niezmiennik:
D(w)⊇[1..i]\ oraz \ D(u)⊇[1..j].