Time complexity of 8-queen, by placeing one by one without attack

Question

I am new to artificial intelligence. I have been trying to analyse the time complexity of 8-queen, by placing one by one without attack.

One approach to achieve goal state is to "add a queen to any square in the leftmost empty column such that it is not attacked by any other queen". And this approach will have a state space of 2057 (also wondering: How to compute this?)

What is the time complexity if I am using Depth First search algorithm (which I think is the most suitable one)? How about the space complexity?

I am puzzled because the brunching of the search tree is reducing greatly when goes deep. $O(8^8)$ looks too much for time complexity, even for worst case.