La fiecare pas, procedura $backtracking$ alege dacă să pună un domino orizontal, unul vertical sau să treacă mai departe, deci o limită superioară ar fi $O(3^M^)$ operaţii (nu toate configuraţiile vor fi posibile). În tablou avem $N x 3^M^$ stări, deci complexitatea algoritmului este $O(N * 9^M^)$. Menţionăm din nou că aceasta este o limită superioară şi că algoritmul se va comporta mult mai bine în practică.

h2(#prob7). Problema 7 ( _Bugs, CEOI 2002_ )

h2(#prob7). Problema 7 ("_Bugs_":http://acm.pku.edu.cn/JudgeOnline/problem?id=1038)

bq. Să se acopere o tablă de dimensiuni $M x N (1 <= M <= 10, 1 <= N <= 150)$ cu un număr maxim de piese de dimensiuni $3 x 2$ şi $2 x 3$. Tabla are unele celule ce trebuie să nu fie acoperite, iar oricare două piese nu se pot suprapune. Pentru tabla de mai jos, numărul maxim de piese cu care se poate acoperi este $3$.