What is the time complexity in big-O notation of Algorithm X? 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.


  
  If the matrix $A$ has no columns, the current partial solution is a valid solution; terminate successfully.
  Otherwise choose a column $c$ (deterministically).
  Choose a row $r$ such that $A_{r,c} = 1$ (nondeterministically).
  Include row $r$ in the partial solution.
  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$.
  
  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.
Its worst-case running time is exponential.

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