I need some help to find out which are the asymptotics (big-O) of the following codes:

\begin{verbatim} void EulerTour(List[] graph, int u, Stack tour) { for (int i = 0; i < graph[u].Count; i++) { var v = graph[u][i]; if (v.Second != 0) //edge hasn't been deleted { v.Second = 0; //deactivate edge for (int j = 0; j < graph[v.First].Count; j++) { //remove edge from v's list var uu = graph[v.First][j]; if (uu.First == u && uu.Second != 0) { uu.Second = 0; //deactivate edge break; } } EulerTour(graph, v.First, tour); } } tour.Push(u); } \end{verbatim}

It looks for an Euler tour in a graph G = (V, E). I have read that this algorithm (cycle finding) is O(|V| + |E|), but I don't know if this specific implementation is that too.

I have this other, using Linked Lists:

\begin{verbatim} void EulerTour(LinkedList[] graph, int u, Stack tour) { while (graph[u].Count > 0) { var v = graph[u].First.Value;

graph[u].RemoveFirst();
    graph[v].Remove(u);

    EulerTour(graph, v, tour);
}
tour.Push(u);

} \end{verbatim}

And I don't know if this one have the same asymptotics that the previous, because it actually removes the edge.

I have one more code:

\begin{verbatim} void EulerTour(LinkedList[] graph, int u, Stack tour) { while (graph[u].Count > 0) { var v = graph[u].First.Value; graph[u].RemoveFirst();

EulerTour(graph, v, tour);
}
tour.Push(u);

} \end{verbatim}

It's idem to the second, but in this case the graph is directed, so here we don't perform the second removal. I think this one should be O(|E|) since it is executed once for each edge, but I'm not sure :(

Please, can someone explain me this asymptotics?