0
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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)$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ The time should be O(E+V) en.wikipedia.org/wiki/Depth-first_search $\endgroup$ – asv May 9 at 10:39
  • $\begingroup$ @asv for explicit graphs yes O(E+V), I described implicit graphs O(b^d). See further down in wikipedia. $\endgroup$ – Koenig Lear May 9 at 10:54
  • $\begingroup$ What means implicit graph? Can you show me how to obtain O(E+V) with recursive relation? Thank you $\endgroup$ – asv May 9 at 11:51
  • 1
    $\begingroup$ @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. $\endgroup$ – Koenig Lear May 9 at 12:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.