Ho un sudoku che realizzo con una matrice

*sudoku[dim*dim][dim*dim]

dove dim è la dimensione del riquadro piccolo di caselle (Regione)

un sudoku del genere ha (dim*dim)^2 righe e (dim*dim)^2
ed ha (dim*dim)^4 caselle, incluse in queste ci possono essere T caselle caselle fisse, ovvero quelle che presentano già un valore inserito che non si puo cambiare.

al valore numerico da inserire nelle caselle posso assegnare un un range di [1... dim*dim]

poi ho un metodo che in Backtracking risolve il puzzle,

la mia domanda è, qual'è la complessità di un algoritmo del genere sia nel caso migliore che nel caso peggiore?

il caso migliore dovrebbe essere, corregetemi se sbaglio O( ((dim^2)-T)^2 )
è corretto?
ed il caso peggiore qual'è?

Grazie infinite!