Essential complexity

Essential complexity refers to a situation where all reasonable solutions to a problem must be complicated (and possibly confusing) because the "simple" solutions would not adequately solve the problem. It stands in contrast to accidental complexity, which arises purely from mismatches in the particular choice of tools and methods applied in the solution.

The term Essential complexity is also used with a different meaning in connection with cyclomatic complexity. In this context, essential complexity refers to the cyclomatic complexity after iteratively replacing all well structured control structures with a single statement. Structures such as if-then-else and while loops are considered well structured. Unconstrained use of goto statements can produce programs which can not be reduced in this way.

For example, the following C program fragment has an essential complexity of 1, because the inner if statement and the for can be reduced:

for(i=0;i<3;i++) { if(a [i] = 0) b [i] += 2; }

The following C program fragment has an essential complexity of more than one. It finds the first row of z which is all zero and puts that index in i; if there is none, it puts -1 in i.

for(i=0;iee also

* Cyclomatic complexity
* Decision-to-decision path
* Occam's Razor
* No silver bullet