4 ms·
The number of edges in a complete graph is n*(n - 1)/2, so by that metric it would be quadratic.
by sage_joch 15y ago
The number of edges in a complete graph is n*(n - 1)/2, so by that metric it would be quadratic.
- lurker19 15y agoYes but the number of nodes is n, and an "interaction" among m nodes might not be decomposable to a chain of pairwise interactions, which raises the ceiling back to exponetial (actually factorial, which is worse).
- scarmig 15y agoWhat corresponds to interactions that aren't decomposable as pairwise interactions? Race conditions? Resource utilization? Real bugs (and the nastier ones), but probably a minority. So factorial with a relatively small constant in front of it. But obviously the real answer is to write a program that will correctly verify all other programs.