The first step of the algorithm involves sorting the objects according to their depth. With quicksort, sorting takes O(n log n) time, and depending on the variation, it could be implemented with using O(n) space, or it could be implemented using O(n) additional space (go here for additional information on quicksort). Step two involves displaying an object, and the assumption is that displaying one object takes O(1) time. Since all objects are rendered, and the assumption is that step two takes O(1) time, step three takes O(n) time. So the entire algorithm takes O(n log n) + O(n) time, with at least O(n) space used.
The painter's algorithm is most suited for situations where the sorting is minimized, such as in scenes where the depth of the objects are easily determinable. The idea is to avoid the n log n sort. In other words, it makes sense to use it when the scene is still, or when a scene moves in a way that the positions of the objects don't move much. Also, because it renders all objects once, whether they are viewable in the final picture or not, it is wasteful if only a few objects are displayed relative to the total number of objects.