3 ms·

without straining my brain, to me its reasonable to measure complexity by number of interacting components, which is a combination, which is geometric, which is

• 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 ago
    Yes 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 ago
      What 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.
• joshhart 15y ago
  It can be quadratic. Think about drawing all possible lines between points (possible components in software): Make a table with columns being # points and the # lines you can draw between them. 1 0 2 1 3 3 (triangle) 4 6 (box with a criss cross) 5 10 (5 point star, with everything connected) ... This relation is n * (n - 1) / 2
• lurker19 15y ago
  Yes, combination, which is factorial, which is yet larger than exponential. Not sure what you mean by "geometric" in this context.