Difference between revisions of "Essential complexity"

Latest revision as of 08:16, 6 September 2016

In computer science, essential complexity is a numerical measure defined by Thomas J. McCabe, Sr. in his highly cited, 1976 paper better known for introducing cyclomatic complexity.

Description

McCabe defined essential complexity as the cyclomatic complexity of the reduced CFG (control flow graph) after iteratively replacing (reducing) all structured programming control structures, i.e. those having a single entry point and a single exit point (for example if-then-else and while loops) with placeholder single statements.

McCabe's reduction process is intended to simulate the conceptual replacement of control structures (and actual statements they contain) with subroutine calls, hence the requirement for the control structures to have a single entry and a single exit point. (Nowadays a process like this would fall under the umbrella term of refactoring.)

All structured programs evidently have an essential complexity of 1 as defined by McCabe because they can all be iteratively reduced to a single call to a top-level subroutine.

As McCabe explains in his paper, his essential complexity metric was designed to provide a measure of how far off this ideal (of being completely structured) a given program was.

Thus greater than 1 essential complexity numbers, which can only be obtained for non-structured programs, indicate that they are further away from the structured programming ideal.

See also

• Cyclomatic complexity
• Decision-to-decision path
• History of software engineering

External links

• Essential complexity @ Wikipedia