Accession Number:

AD0729011

Title:

Complexity Measures for Programming Languages.

Descriptive Note:

Master's thesis,

Corporate Author:

MASSACHUSETTS INST OF TECH CAMBRIDGE PROJECT MAC

Personal Author(s):

Report Date:

1971-09-01

Pagination or Media Count:

87.0

Abstract:

A theory of complexity is developed for algorithms implemented in typical programming languages. The complexity of a program may be interpreted in many ways a method for measuring a specific type of complexity is a complexity measure -- some function of the amount of a particular resource used by a program in processing an input. After the complexity of the basic program elements is determined, program complexity is analyzed with respect to single inputs and then with respect to finite sets of legitimate halting inputs. A program equation is developed to aid in the complexity analysis. Using this equation, an input set is partitioned into classes of constant complexity. Several equivalence relations are defined, relating different programs by their complexity. Complexity is also discussed in terms of concatenation and functional equivalence of program. Author

Subject Categories:

  • Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE