How to calculate time complexity of backtracking algorithm?

In short:

1. Hamiltonian cycle : O(N!) in the worst case
2. WordBreak and StringSegment : O(2^N)
3. NQueens : O(N!)

Note: For WordBreak there is an O(N^2) dynamic programming solution.

---

More details:

1. In Hamiltonian cycle, in each recursive call one of the remaining vertices is selected in the worst case. In each recursive call the branch factor decreases by 1. Recursion in this case can be thought of as n nested loops where in each loop the number of iterations decreases by one. Hence the time complexity is given by:T(N) = N*(T(N-1) + O(1))
T(N) = N*(N-1)*(N-2).. = O(N!)
2. Similarly in NQueens, each time the branching factor decreases by 1 or more, but not much, hence the upper bound of O(N!)
3. For WordBreak it is more complicated but I can give you an approximate idea. In WordBreak each character of the string has two choices in the worst case, either to be the last letter in the previous word, or to be the first letter of a new word, hence the branching factor is 2. Therefore for both WordBreak & SegmentString T(N) = O(2^N)