eddy's blog

Help with asymptotics...
By eddy, history, 9 years ago, In English

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

void EulerTour(List<Pair>[] graph, int u, Stack<int> 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);
}

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:

void EulerTour(LinkedList<int>[] graph, int u, Stack<int> 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);
}

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:

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

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

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 these asymptotics?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

NO HABLEN TODOS A LA VEZ!!!

→ Reply
»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

First two implementations suffer from the following problem: they find 'reverse' of the edge in linear time, which may result in O(E2). Worst case is a 'star' graph with some additions, I think.

Second implementation does not differ much from the first, as the only extra action is to remove an already found item from linked list, which is O(1).

Third implementation, however, is O(|E|) for the very reason you mentioned: there are a single 'starting' call of EulerTour and each iteration of the inner loop removes a single edge of the source graph, so there can be not more than O(|E|) iterations in total (and, as a consequence, no more than O(|E|) calls of EulerTour in total).

Second implementation can be healed if you pre-calculate position of the 'reverse' edge for each edge in the graph. If so, it will become will be O(|E|).

Fixing first implementation is a bit more tricky: you still go through first unused edges each time you enter a vertex. So, if you have a vertex of degree k, it will take O(k2) iterations in total to process all adjacent edges. Fix is to remember the number of first probably unused edge for each vertex.

→ Reply