A formal program complexity model and its application

TitleA formal program complexity model and its application
Publication TypeJournal Articles
Year of Publication1992
AuthorsTian J, Zelkowitz MV
JournalJournal of Systems and Software
Pagination253 - 266
Date Published1992/03//
ISBN Number0164-1212

This article takes an axiomatic approach to defining program complexity using complexity rankings and measures. A complexity ranking is an abstract, qualitative comparison between programs that is approximated by a complexity measure on each program. A set of axioms are stated and a classification scheme is presented with properties of each class. This is extended a series of properties developed by Weyuker. The formal model has many applications, including evaluating and classifying existing complexity measures and serving as criteria for complexity measure selection.