What is the time complexity in big-O notation of Algorithm X?

Question

Knuth's Algorithm X is a recursive, nondeterministic, depth-first, backtracking algorithm that solves the NP-complete problem exact cover (EC). (It actually finds all solutions to EC.)

I do not understand how such algorithm could do that. What is the time complexity of this algorithm in terms of big-O notation?

Here is the algorithm from Wikipedia.

1. If the matrix $A$ has no columns, the current partial solution is a valid solution; terminate successfully.
2. Otherwise choose a column $c$ (deterministically).
3. Choose a row $r$ such that $A_{r,c} = 1$ (nondeterministically).
4. Include row $r$ in the partial solution.

5. For each column $j$ such that $A_{r,j} = 1$,

   • for each row $i$ such that $A_{i,j} = 1$,

     • delete row $i$ from matrix $A$.

   • delete column $j$ from matrix $A$.

6. Repeat this algorithm recursively on the reduced matrix A.

Step 3 of the algorithm is done nondeterministically. What does this mean? (I think this is the point why I cannot find the big-O complexity of the algorithm.)

An implementation of Algorithm X in python can be found in Algorithm X in 30 lines! where I cannot find the nondeterministic choice of step 3.

Answer 1

Its worst-case running time is exponential.

By "nondeterministic", this essentially means "try all possibilities".