Noi vom intersecta mereu o multime de intervale cu un interval de forma (x-D,x+D) care se va transpune in 1 sau 2 intervale necirculare, adica Y[i].size() va fi mereu 1 sau 2. Complexitatea functie de mai sus este astfel <tex>O(N*M)</tex>.

Acum, modul in care vom parcurge intersectiile va dicta complexitatea finala. Daca pur si simplu iteram prin cele 2^M configuratii iar pentru fiecare configuratie construim intersectia intervalelor din configuratie de la 0, complexitatea va fi <tex>O(N*M^2^ *2^M^)</tex>.

Acum, modul in care vom parcurge intersectiile va dicta complexitatea finala. Daca pur si simplu iteram prin cele 2^M configuratii iar pentru fiecare configuratie construim intersectia intervalelor din configuratie de la 0, complexitatea va fi <tex>O(N*M^2^*2^M^)</tex>.

Complexitatea care rezolva problema este <tex>O(N*M*2^M^)</tex> care poate fi obtinuta prin metoda backtracking: Construim treptat intersectia si mentinem o stiva cu starea intersectiilor la fiecare pas. La pasul pasul i alegem daca sa adaugam sau nu al i-lea cod din cele M la configuratia curenta. Daca nu-l adaugam, cream un nou nivel pe stiv in care starea intersectiilor este aceeasi. Daca il adaugam, cream un nou nivel pe stiva in care starea intersectiilor este rezultatul apelarii functiei _intersect_(starea curenta, al i-lea cod). In ambele cazuri trecem la pasul i+1 iar cand ne intoarcem avem salvata pe stiva starea de la care am plecat.