Rigorous definition and analysis of program complexity measures: An example using nesting
Abstract Two deficiencies persist in program complexity measures research: a lack of formalism in defining complexity measures and a lack of analytical tools for evaluating these measures. The lack of formalism significantly hinders independent empirical evaluations of proposed measures. The lack of analytical tools and techniques for evaluating measures makes comparisons between independent research efforts difficult. As an example of one attempt to avoid these deficiencies, we formally define “nesting” for arbitrary (not necessarily well-structured) programs and use this definition to redefine four existing measures of nesting that have appeared in the literature. We then define one simple tool that can be used to evaluate nesting measures. Application of this tool to the redefined measures reveals in one case that the proposed measure does not adequately quantify the nesting represented by the simple tool. In the other three cases the measures are demonstrably similar. Analogous analytical evaluations of proposed measures prior to the requisite empirical studies are encouraged.