Este tema lo tengo bastante oxidado, pero creo recordar que la complejidad del backtracking depende del problema que tengas que resolver. Si haces un árbol de posibilidades en un caso sencillo puede tener un máximo de complejidad de n! o incluso n elevado a n.
De todas formas, había condiciones de poda (puntos en los que no continuabas el proceso y hacías la "marcha atrás" del backtracking) para no seguir explorando posibilidades que ya se saben incorrectas, aunque no recuerdo si a eso se le seguía llamando backtracking o era otro algoritmo distinto.
En el ejemplo del sudoku de Istarion, sabiendo que en la misma fila (o columna o cuadro, según estés generando el árbol de la solución) no puedes repetir un número, cuando el siguiente paso del algoritmo implica repetir puedes "hacer la poda".
Todo esto suponiendo, claro, que el problema sea computable.
Por cierto, en casos de recursividad, creo que la mejor forma de analizar la complejidad es por los nodos computados poniendo un ejemplo sencillo (por ejemplo, mezcla ordenada de dos listas de tres elementos)
