A Complexity Measure
Abstract
This paper describes a graph-theoretic complexity measure and illustrates how it can be used to manage and control program complexity. The paper first explains how the graph-theory concepts apply and gives an intuitive explanation of the graph concepts in programming terms. The control graphs of several actual Fortran programs are then presented to illustrate the correlation between intuitive complexity and the graph-theoretic complexity. Several properties of the graph-theoretic complexity are then proved which show, for example, that complexity is independent of physical size (adding or subtracting functional statements leaves complexity unchanged) and complexity depends only on the decision structure of a program.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Cyclomatic complexity is a software complexity measure based on the decision structure of code.
“Cyclomatic complexity is a software complexity measure that is based on the decision structure of the code (McCabe, 1976).”
From Relative Feedback Increases Disparities in Effort and Performance in Crowdsourcing Contests (2022) · cites this paper as McCabe, 1976
McCabe's cyclomatic complexity was used to measure code complexity.
“The complexity of the source code was measured using cyclomatic complexity, as introduced by Thomas J. McCabe (McCabe, 1976).”
From Relative Feedback Increases Disparities in Effort and Performance in Crowdsourcing Contests (2022) · cites this paper as McCabe, 1976
The study measured code complexity using two standard proxies: source lines of code (SLOC) and McCabe's cyclomatic complexity (CC).
“We measure two standard proxies for code complexity of the Python programs produced by our study participants in each of their assigned tasks, i.e., the number of source lines of code (SLOC) and McCabe's cyclomatic complexity (CC), a measure of the number of linearly independent paths through a program's source code [75]”
From In-IDE Code Generation from Natural Language: Promise and Challenges (2022) · cites this paper as [75]
Cites
Welsh, D. J. A. (1974) · Bulletin of the London Mathematical Society · doi:10.1112/blms/6.2.218b · Cited by 1,056 · see citing works
Structured Programming with go to Statements
Knuth, D. E. (1974) · ACM Computing Surveys · doi:10.1145/356635.356640 · Cited by 678 · see citing works
Software and Its Impact: A Quantitative Assessment
BOEHM, B. W. (1972) · Cited by 266 · see citing works
Mathematical Foundations for Structured Programming
Mills, H. D. (1972) · Cited by 116 · see citing works
A genealogy of control structures
Ledgard, H., & Marcotty, M. (1975) · Communications of the ACM · doi:10.1145/361219.361222 · Cited by 102 · see citing works
Analysis of structured programs
Kosaraju, S. R. (1974) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(74)80043-7 · Cited by 87 · see citing works
Hi-PASS: a computer-aided synthesis system for maximally parallel digital signal processing ASICs
Duncan, P. J., Swamy, S. L. N., Sprouse, S., et al. (1992) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.1992.226547 · Cited by 8 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
A Python library for probabilistic analysis of single-cell omics data
Gayoso, A., Lopez, R., Xing, G., Boyeau, P., Valiollah Pour Amiri, V., Hong, J., Wu, K., Jayasuriya, M., Mehlman, E., Langevin, M., et al. (2022) · Nature Biotechnology · doi:10.1038/s41587-021-01206-w · Cited by 789 · see citing works
A systematic review of machine learning techniques for software fault prediction
Malhotra, R. (2015) · Applied Soft Computing · doi:10.1016/j.asoc.2014.11.023 · Cited by 620 · see citing works
Automated Grading and Feedback Tools for Programming Education: A Systematic Review
Messer, M., Brown, N. C. C., Kölling, M., & Shi, M. (2024) · ACM Transactions on Computing Education · doi:10.1145/3636515 · Cited by 262 · see citing works
Understanding understanding source code with functional magnetic resonance imaging
Siegmund, J., Kästner, C., Apel, S., Parnin, C., Bethmann, A., Leich, T., Saake, G., & Brechmann, A. (2014) · Proceedings of the 36th International Conference on Software Engineering · doi:10.1145/2568225.2568252 · Cited by 219 · see citing works
Subjective evaluation of software evolvability using code smells: An empirical study
Mäntylä, M. V., & Lassenius, C. (2007) · Empirical Software Engineering · doi:10.1007/s10664-006-9002-8 · Cited by 171 · see citing works
In-IDE Code Generation from Natural Language: Promise and Challenges
Xu, F. F., Vasilescu, B., & Neubig, G. (2022) · ACM Transactions on Software Engineering and Methodology · doi:10.1145/3487569 · Cited by 154 · see citing works
A survey of AIOps methods for failure management
Notaro, P., Cardoso, J., & Gerndt, M. (2021) · ACM Transactions on Intelligent Systems and Technology · doi:10.1145/3483424 · Cited by 142 · see citing works
Mafarja, M., Thaher, T., Al-Betar, M. A., Too, J., Awadallah, M. A., Abu Doush, I., & Turabieh, H. (2023) · Applied Intelligence · doi:10.1007/s10489-022-04427-x · Cited by 91 · see citing works
SWE-bench: Can Language Models Resolve Real-World GitHub Issues?
Jimenez, C. E., Yang, J., Wettig, A., Yao, S., Pei, K., Press, O., & Narasimhan, K. (2023) · arXiv · doi:10.48550/arxiv.2310.06770 · Cited by 72 · see citing works
Towards an Analysis of Program Complexity From a Cognitive Perspective
Duran, R., Sorva, J., & Leite, S. (2018) · Proceedings of the 2018 ACM Conference on International Computing Education Research · doi:10.1145/3230977.3230986 · Cited by 44 · see citing works
Bhatia, S., Gandhi, T., Kumar, D., & Jalote, P. (2024) · Proceedings of the 1st International Workshop on Large Language Models for Code · doi:10.1145/3643795.3648396 · Cited by 55 · see citing works
Social engineering in social networking sites: Affect-based model
Algarni, A., Xu, Y., Chan, T., & Tian, Y.-C. (2013) · 8th International Conference for Internet Technology and Secured Transactions (ICITST-2013) · doi:10.1109/icitst.2013.6750253 · Cited by 41 · see citing works
Weisz, J. D., Kumar, S. V., Muller, M., Browne, K.-E., Goldberg, A., Heintze, K. E., & Bajpai, S. (2025) · Proceedings of the Extended Abstracts of the CHI Conference on Human Factors in Computing Systems · doi:10.1145/3706599.3706670 · Cited by 37 · see citing works
<uri>Jutge.org</uri>: Characteristics and Experiences
Petit, J., Roura, S., Carmona, J., Cortadella, J., Duch, J., Gimenez, O., Mani, A., Mas, J., Rodriguez-Carbonell, E., Rubio, E., et al. (2018) · IEEE Transactions on Learning Technologies · doi:10.1109/tlt.2017.2723389 · Cited by 33 · see citing works
Landman, D., Serebrenik, A., Bouwers, E., & Vinju, J. J. (2016) · Journal of Software: Evolution and Process · doi:10.1002/smr.1760 · Cited by 29 · see citing works
Focus-shifting patterns of OSS developers and their congruence with call graphs
Xuan, Q., Okano, A., Devanbu, P., & Filkov, V. (2014) · Proceedings of the 22nd ACM SIGSOFT International Symposium on Foundations of Software Engineering · doi:10.1145/2635868.2635914 · Cited by 27 · see citing works
Does ChatGPT Help Novice Programmers Write Better Code? Results From Static Code Analysis
Haindl, P., & Weinberger, G. (2024) · IEEE Access · doi:10.1109/access.2024.3445432 · Cited by 25 · see citing works
Effects of Test-Driven Development: A Comparative Analysis of Empirical Studies
Mäkinen, S., & Münch, J. (2014) · Lecture Notes in Business Information Processing · doi:10.1007/978-3-319-03602-1_10 · Cited by 18 · see citing works
Relative Feedback Increases Disparities in Effort and Performance in Crowdsourcing Contests
Tsvetkova, M., Müller, S., Vuculescu, O., Ham, H., & Sergeev, R. A. (2022) · Proceedings of the ACM on Human-Computer Interaction · doi:10.1145/3555649 · Cited by 8 · see citing works
Computing Education Research Today
Fincher, S. A., Tenenberg, J., Dorn, B., Hundhausen, C., McCartney, R., & Murphy, L. (2019) · The Cambridge Handbook of Computing Education Research · doi:10.1017/9781108654555.003 · Cited by 7 · see citing works
- Authors
- McCabe, T. J.
- Affiliations
- National Security Agency (US)
- Corresponding author
- McCabe, T.J.
- Venue
- IEEE Transactions on Software Engineering
- Published
- 1976-12
- Volume
- SE-2
- Issue
- 4
- Pages
- 308-320
- ISSN
- 0098-5589 (ISSN-L)
- 1939-3520
- 2326-3881
- OpenAlex
- W1964962870
- Cited by
- 6,059
- References
- 7
- Citations by year
- 2026: 210 · 2025: 189 · 2024: 177 · 2023: 203 · 2022: 175 · 2021: 227 · 2020: 244 · 2019: 312 · 2018: 232 · 2017: 220 · 2016: 262 · 2015: 250 · 2014: 233 · 2013: 248 · 2012: 249
- FWCI
- 146.40
- Type
- journal article
- Language
- en
- Open access
- closed
- Licence
- Locations
- IEEE Transactions on Software Engineering (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Information Systems › Software Engineering Research
- Physical Sciences › Computer Science › Software › Software Reliability and Analysis Research
- Physical Sciences › Computer Science › Artificial Intelligence › Logic, programming, and type systems
- Keywords
- software complexity, control flow graph, FORTRAN program, decision structure, control flow, complexity measures
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
