Každé volanie funkcie dfs() samo o sebe prefarbí jeden vrchol.
Celkový počet volaní teda bude rovný počtu prefarbených vrcholov
(čiže nanajvýš $n$). Každé volanie urobí (okrem rekurzívnych volaní)
množstvo práce úmerné počtu hrán vedúcich zo $Z$.
Keďže z do každého vrchola sa dfs() volá najviac raz,
každú hranu takto kontrolujeme najviac raz (v prípade orientovaných hrán),
resp. dvakrát (v prípade neorientovaných hrán).
To znamená, že v najhoršom prípade má náš algoritmus časovú zložitosť $O(n+m)$,
kde $n$ je počet vrcholov grafu a $m$ je počet hrán.
Presnejší odhad dostaneme, ak namiesto počtu všetkých vrcholov vezmeme
iba počet navštívených (teda dosiahnuteľných z $S$) a namiesto počtu
všetkých hrán vezmeme iba počet dosiahnuteľných hrán.
Na pamätanie grafu potrebujeme aspoň $O(m)$ pamäte. Niekedy si však graf pamätáme aj z iných dôvodov a teda ho nemusíme počítať do pamäťovej zložitosti prehľadávania do hĺbky. V takom prípade má prehľadávanie pamäťovú zložitosť $O(n)$, kvôli zásobníku počas rekurzie.