Question

What's the time complexity of this algorithm?
http://stackoverflow.com/a/4028855/1230219

Answer 1

Context: I'm trying to write an educational circuit solver and I need to use chordless cycles to make a cycle basis which is equivalent to mesh analysis in circuit analysis. I am curious at what point my simulator will more or less break down due to too much complexity.

Answer 2

Can you expand a little on your choice of chordless cycles? What if the circuit has cycles less than five (as in parallel resistors), then you will need to put dummy edges and hence increase complexity, which also depends on the operations performed on the graph.

Answer 3

Hmm, if you draw an example in question I'll try to point out how I would do the analysis.

Answer 4

Wait, it looks like people are having differing definitions of chordless cycles. I use cycles at least four, since 3 will never have chords, so excluded. Some others will accept 3-edge cycles. Which one do you adopt?

Answer 5

Well from my standpoint, I will have to adopt 3 edge cycles, as they are a necessary component in mesh analysis.

Answer 6

Exactly, so I withdraw my previous enquiry.
A first glance seems to tell me the algo from your link has a complexity of \(dim^3\) since loops are nexted 3-deep.

Answer 7

This is an interesting CS problem. I suggest you repost in CS section to get the opinions of many others knowlegeable and interested in the subject.

Answer 8

.

Answer 9

Well, I looked at it again, and the structure is actually more than three-deep. :(
The number preceding the loop is the level number.
1.for
2. for
3. for
while (pop may eventually be re-pushed)
4. for
5. find
for
if
6. for
So I see a mininum of 6 deep, so ndim^6, assuming the find statement should be counted as linear with ndim. However, I have not counted the push and the pops, which I believe could raise the power one more deep. In any case, it is polynomial O(n^6) or O(n^7).
Sorry for the previous rushed conclusion.