# Time complexity of DFS and recurrence relation

Is it possible to compute time complexity of Depth First Search (recursive version) which is O(E+V) using a recurrence relation?

For an implicit graph the recurrence can be written as follows:

Let $$b$$ be the number of branches of every node (assumed to be constant)

let $$d$$ the depth of the graph

For depth 1 there are $$b$$ branches:

$$T(b,1) = b$$

For the next levels it can be written as

$$T(b,d) = b + b*T(b,d-1)$$

where $$b$$ are the nodes at this level, and are the $$b*T(b,d-1)$$ nodes at next level.

If you substitute the definition for $$T(b,d-1)$$ you get

$$b * (1 + b*(1+T(b,d-2)) = b + b^2(1+T(b,d-2))$$

If you further substitute the definition of $$T(b,d-2)$$ you get

$$b + b^2(1+b+b*T(b,d-3)) = b + b^2 + b^3 + b^3*T(b,d-3)$$

If you continue to expand you get

$$T(b,d) = b + b^2 +b^3 +... + b^{d-1}*T(b,1)$$

Since we know that $$T(b,1) = b$$, we can substitute

$$T(b,d) = b + b^2 +b^3 +... + b^{d-1}*b$$

Thus

$$T(b,d) = b + b^2 +b^3 +... + b^d$$

Using Big-O Notation. $$O(b^d)$$

For explicit graphs with $$V$$ vertex and $$E$$ edges

We assume you have an adjacent list. That is for every $$V$$ you have a list of adjacent edges. You can think of a Table of $$E$$ edges (columns) x $$V$$ vertex (rows).

We can write our recurrent relation based on the navigation of that table.

$$T(V,E) = 1 + e_0 + T(V-e_0,E-e_0)$$

We count $$1$$ for visiting the first row, and $$e_0$$ for the number of edges adjacent to that first vertex. For the next rows we use the recurrent relation except this time we have $$V-e_0$$ vertex and $$E-e_0$$ edges to visit.

If we substitute our definition for the 3rd. element in our relation we get:

$$T(V,E) = 1 + e_0 + 1 + e_1 + T(V-e_1,E-e_1)$$

if you keep expanding you get

$$T(V,E) = 1 + 1 + .. + 1 + e_0 +e_1 + .. + e_V$$

1 for every row visited and a certain number of edges for a given vertex. In total the number of edges is $$E =e_0 + e_1 + .. e_V$$.

$$T(V,E) = V + E$$

in Big-O Notation $$O(V+E)$$.

• The time should be O(E+V) en.wikipedia.org/wiki/Depth-first_search – asv May 9 at 10:39
• @asv for explicit graphs yes O(E+V), I described implicit graphs O(b^d). See further down in wikipedia. – Koenig Lear May 9 at 10:54
• What means implicit graph? Can you show me how to obtain O(E+V) with recursive relation? Thank you – asv May 9 at 11:51
• @asv an explicit graph is one where you beforehand know the exact number of vertex and edges. In an implicit graph you don't know them. They're determined algorithmically with a branching factor b. Anyway, see my updated answer for the complexity of explicit graphs. – Koenig Lear May 9 at 12:21