Time complexity of this solution to N-queens problem
Your analysis would be reasonable for rooks, but not for queens. For example, in the second row there are not n-1 possible positions, but n-2 in two cases and n-3 in most cases. Now big-O provides an upper bound, but it is an upper bound that vastly overestimates the effort needed.