We all know the algorithm that solves the Generalized Geography problem using polynomial space (it's described on wiki). My question is: what is the time complexity of this algorithm? I'd like a more precise answer than just 'polynomial'. As far as I understand, we're making $|V|$ calls at most? We won't call the function from the same node more than once because nodes are deleted once visited. And we also have to estimate how much does one iteration take, which, I assume, would be $O(|E|)$ since we're going through all vertices connected to the current one? So that would make the overall time complexity $O(|V|\cdot|E|)$.
I'm also curious about exact space complexity, not just 'polynomial' (I can see that), but something precise like $O(|V|^2)$. If I understand correctly, recursion depth in $O(|V|)$, would that mean that overall space complexity is $O(|V|)$ or am I missing something here?