Анализ поиска в глубину¶

В общем случае время выполнения поиска в глубину следующее. Оба цикла в dfs выполняются за $O(V)$ (без учёта происходящего в dfsvisit), поскольку они вычисляются по одному разу для каждой вершины графа. Цикл в dfsvisit вычисляется один раз для каждого ребра из списка смежности текущей вершины. Поскольку dfsvisit вызывается рекурсивно только в том случае, если вершина окрашена в белый, то цикл для каждого ребра графа выполнится максимум единожды ($O(E)$). Таким образом, общее время выполнения поиска в глубину равно $O(V + E)$.