Per me tuttedue O(V).
Non conta il numero di archi, perchè visitando in profondità un grafo, ogni nodo viene visitato solo se non era già stato visitato in precedenza.
In totale ogni nodo viene visitato solo una volta anche se il grafo è denso.
Questo è abbastanza per dire che la complessità è O(V), anche se la dimostrazione formale è un' altra storia.