Time Complexity

[Moussa Mansour]

Hello Everybody, 

    Someone know the time complexity of the Biofabric Technique?

Best regards

[William Longabaugh]

The default layout is just breadth-first search, so that should
theoretically be O(v+e). But there is also a sorting by degree step that
implies O(v * log v) best case for that part, and the edges need to be
ordered as well to create the wedges, implying O(e * log e). So maybe
(guessing here....) O((v * log v) + (e * log e))? Intersection testing
can be made O(log v + log e) if done right. That being said, I'm going
to bet that there are some really dumb steps in the implementation that
make stuff O(n^2) or even worse; Version 1.0 was not seriously optimized.

The more complex layout algorithm is worse, of course.

Bill

> --
> You received this message because you are subscribed to the Google
> Groups "BioFabric-users" group.
> To unsubscribe from this group and stop receiving emails from it, send
> an email to biofabric-use...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.