Measuring prime program complexity

This paper uses the prime program decomposition of a program as the basis for a measure that closely correlates with our intuitive notion of program complexity. This measure is based upon the information theory ideas of randomness and entropy such that results about structured programming, data abstractions, and other programming paradigms can be stated in quantitative terms, and empirical means can be used to validate the assumptions used to develop the model. As a graph-based model, it can be applied to several graphical examples as extensions not otherwise available to source-code based models. This paper introduces the measure, derives several properties for it, and gives some simple examples to demonstrate that the measure is a plausible approximation of our notions concerning structured programming.