Time Complexity to find a sink in a simple digraph

Thread view:

Marion - 15 Mar 2008 05:16 GMT

Hello all,

I need to find an algorithm (then implement that in java later) that
will find a sink in a simple digraph. I have it pretty much figured
out but I'm confused how to figure out the time complexity.

This is what I'm thinking:
In a graph of n vertices, I will put each vortex into an adjacency
list (will use a linked list to store values) and so there are n(n-1)/
2 possible edges. The way I see it is, n(n-1)/2 is O(n^2) time
complexity I'm hoping not!

Then to examine my adjacency list that would be O(n) time complexity.
(where n = number of Vertices)

So my total time complexity is O(n) + O(n^2) which reduces to O(n^2)?
That doesn't seem right somehow. I don't know how to tell if I'm
analyzing this problem correctly.

Any hints are appreciated.
-m

Reply to this Message

Mark Space - 15 Mar 2008 05:40 GMT

> Hello all,
>
[quoted text clipped - 17 lines]
> Any hints are appreciated.
> -m

It seems to me that you can examine each node as you build the adjacency
list, getting rid of the O(n) term. The O(n^2) ... well I'm not sure,
but it seem fairly rare that you would have a graph where each node is
connected to nearly every other node. Might help if you can predict
what sort of data you'll be analyzing. Lots of edges, or just a few per
node?

Reply to this Message

Roedy Green - 15 Mar 2008 07:43 GMT

>I need to find an algorithm (then implement that in java later) that
>will find a sink in a simple digraph. I have it pretty much figured
>out but I'm confused how to figure out the time complexity.

These algorithms are not specific to a particular language. Try
broadening your search to find a description of the algorithm.

If you are really stuck, go to a university books store and look for a
text book on graph theory. There was lots published on this even back
in the 60s, so you don't need the latest and greatest.

Signature

Roedy Green Canadian Mind Products
The Java Glossary
http://mindprod.com

Reply to this Message

Marion - 15 Mar 2008 09:04 GMT

On Mar 14, 8:43 pm, Roedy Green <see_webs...@mindprod.com.invalid>
wrote:

> >I need to find an algorithm (then implement that in java later) that
> >will find a sink in a simple digraph. I have it pretty much figured
[quoted text clipped - 10 lines]
> Roedy Green Canadian Mind Products
> The Java Glossaryhttp://mindprod.com

True, this topic is not specific to Java but I'm desperate. :p Plus I
know there's LOTS of smart ppl out there that are of the Java type.

I need to find an algorithm that solves this sink detection that is
less than O(n^2) so I think I"m going to have to discard the adjacency
matrix idea. There appears no way around inspecting every edge in
that scenario even though I feel like I should be able to. hrmm.

Thanks your replies, guys. :D

Reply to this Message

Patricia Shanahan - 15 Mar 2008 13:50 GMT

> On Mar 14, 8:43 pm, Roedy Green <see_webs...@mindprod.com.invalid>
> wrote:
[quoted text clipped - 15 lines]
> True, this topic is not specific to Java but I'm desperate. :p Plus I
> know there's LOTS of smart ppl out there that are of the Java type.

There are also some rather smart people over in comp.theory, where the
time complexity of various algorithms is a common subject of discussion.

> I need to find an algorithm that solves this sink detection that is
> less than O(n^2) so I think I"m going to have to discard the adjacency
> matrix idea. There appears no way around inspecting every edge in
> that scenario even though I feel like I should be able to. hrmm.

You have to do one of two things to reduce the complexity:

1. Avoid looking at every edge. In general, a graph with n vertices can
have O(n^2) edges. This may be difficult, because the last edge you look
at for a given node may be the one that prevents it from being a sink,
but there may be something.

Note that the building of an adjacency list is irrelevant. What matters
is looking at each edge, no matter how little you do with it.

2. Restrict the set of graphs. Your current algorithm is O(|V|+|E|)
where V is the vertex set and E is the edge set. If the average number
of edges per vertex does not increase with graph size then |E| is O(|V|)
and you have your O(n) algorithm.

Patricia

Reply to this Message

Joshua Cranmer - 16 Mar 2008 14:20 GMT

> Hello all,
>
[quoted text clipped - 10 lines]
> Then to examine my adjacency list that would be O(n) time complexity.
> (where n = number of Vertices)

With respect to graphs, time and space complexity is not typically
measured in terms of n but in terms of |E| and |V| (or just E and V, but
the former is more correct), the number of edges and the number of
vertices respectively.

|E| is bounded in triangular fashion by |V| in the worst case, but more

often, O(|E|) is about O(|V|), growing linearly or nearly so.

One final point: sparse graphs are generally where |V| <= log |E|
(approximately) and dense graphs are |V| >> log |E|.

> So my total time complexity is O(n) + O(n^2) which reduces to O(n^2)?
> That doesn't seem right somehow. I don't know how to tell if I'm
> analyzing this problem correctly.

My guess is that your answer is O(|V| + |E|).

Signature

Beware of bugs in the above code; I have only proved it correct, not
tried it. -- Donald E. Knuth

Reply to this Message

Time Complexity to find a sink in a simple digraph

Free Magazines