Towards an Analysis of Program Complexity From a Cognitive Perspective
The DOI matches its Crossref record; 85 of the 85 references it cites were found in a registry or an index.
Abstract
Instructional designers, examiners, and researchers frequently need to assess the complexity of computer programs in their work. However, there is a dearth of established methodologies for assessing the complexity of a program from a learning point of view. In this article, we explore theories and methods for describing programs in terms of the demands they place on human cognition. More specifically, we draw on Cognitive Load Theory and the Model of Hierarchical Complexity in order to extend Soloway's plan-based analysis of programs and apply it at a fine level of granularity. The resulting framework of Cognitive Complexity of Computer Programs~(CCCP) generates metrics for two aspects of a program: plan depth and maximal plan interactivity. Plan depth reflects the overall complexity of the cognitive schemas that are required for reasoning about the program, and maximal plan interactivity reflects the complexity of interactions between schemas that arise from program composition. Using a number of short programs as case studies, we apply the CCCP to illustrate why one program or construct is more complex than another, to identify dependencies between constructs that a novice programmer needs to learn and to contrast the complexity of different strategies for program composition. Finally, we highlight some areas in computing education and computing education research in which the CCCP could be applied and discuss the upcoming work to validate and refine the CCCP and associated…
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Citations
Cites
Cognitive Load During Problem Solving: Effects on Learning
Sweller, J. (1988) · Cognitive Science · doi:10.1016/0364-0213(88)90023-7 · Cited by 11,048 · cited 8×
“The first is schema theory and the related Cognitive Load Theory (CLT) [2, 10, 80], which are concerned with the limitations of working memory and the growth of expertise as schemas in long-term memory; here we extend the earlier work in CER by Soloway, Rist, and others”
BackgroundResultInfluentialMcCabe, T. J. (1976) · IEEE Transactions on Software Engineering · doi:10.1109/tse.1976.233837 · Cited by 6,059
The Taxonomy of Educational Objectives
(2012) · Encyclopedia of the Sciences of Learning · doi:10.1007/978-1-4419-1428-6_6027 · Cited by 4,103
Cognitive Load Measurement as a Means to Advance Cognitive Load Theory
Paas, F., Tuovinen, J. E., Tabbers, H., & Van Gerven, P. W. M. (2003) · Educational Psychologist · doi:10.1207/s15326985ep3801_8 · Cited by 2,527
Element Interactivity and Intrinsic, Extraneous, and Germane Cognitive Load
Sweller, J. (2010) · Educational Psychology Review · doi:10.1007/s10648-010-9128-5 · Cited by 2,020 · cited 2×
“depends on external factors such as engagement [40, 81].”
BackgroundRobinson, P. (2001) · Applied Linguistics · doi:10.1093/applin/22.1.27 · Cited by 1,273 · cited 1×
“Establishing a theoretically motivated, empirically sustainable, and pedagogically feasible methodology for sequencing topics by complexity is one of the major goals in curriculum development [64].”
BackgroundAccess to information in working memory: Exploring the focus of attention.
Oberauer, K. (2002) · Journal of Experimental Psychology Learning Memory and Cognition · doi:10.1037//0278-7393.28.3.411 · Cited by 1,161 · cited 17×
“1 Which plans fall within the RDA of a particular FoA depends on the way plans are merged, sequenced, and nested.”
BackgroundMethodInfluentialOn the capacity of attention: Its estimation and its role in working memory and cognitive aptitudes
Cowan, N., Elliott, E. M., Scott Saults, J., Morey, C. C., Mattox, S., Hismjatullina, A., & Conway, A. R. A. (2005) · Cognitive Psychology · doi:10.1016/j.cogpsych.2004.12.001 · Cited by 1,144 · cited 1×
“We build on the concept of focus of attention (FoA) [18, 60], which we have adapted to a programming context.”
MethodEvaluating the Quality of Learning: The Solo Taxonomy : Structure of the Observed Learning Outcome
Biggs, J., & Collis, K. F. (1977) · Cited by 1,079
Development of an instrument for measuring different types of cognitive load
Leppink, J., Paas, F., Van der Vleuten, C. P. M., Van Gog, T., & Van Merriënboer, J. J. G. (2013) · Behavior Research Methods · doi:10.3758/s13428-013-0334-1 · Cited by 1,066 · cited 1×
“However, there is an instrument for estimating cognitive load from learners’ ratings of perceived mental effort after a learning task [42], which has been adapted for programming tasks [57].”
Method
Research works printed but not linked: 9
- Michael Lamport Commons, JA Rodriguez, PM Miller, SN Ross, A LoCicero, EA Goodheart, and D Danaher-Gilpin . 2007. Applying the model of hierarchical complexity. Unpublished manuscript (2007).
- 10.5555/2483716.2483726 · doi:10.5555/2483716.2483726
- 10.5555/2483716.2483722 · doi:10.5555/2483716.2483722
- W. Lewis Johnson, Elliot Soloway, Benjamin Cutler, and Steven Draper . 1983. Bug Catalogue: I. Technical Report. Yale University, YaleU/CSD/RR \#286.
- Sofia Leite Jose Carlos Principe Antonio Carlos Silva Joao Marques-Teixeira Michael L Commons and Pedro Rodrigues . In Review. Connectionist models capture hierarchical complexity transitions in development: discrimination between memory-based and operationally-based transitions. (. In Review).
- 10.5555/2459936.2459938 · doi:10.5555/2459936.2459938
- 10.1037/0278-7393.28.3.411 · DOI · Paper page
- 10.1207/s15516709cog1303_3 · doi:10.1207/s15516709cog1303_3 · Paper page
- Yvonne Rogers . 2004. New theoretical approaches for HCI. Annual review of information science and technology Vol. 38, 1 (2004), 87--143.
Cited by
Studying the effect of AI Code Generators on Supporting Novice Learners in Introductory Programming
Kazemitabaar, M., Chow, J., Ma, C. K. T., Ericson, B. J., Weintrop, D., & Grossman, T. (2023) · Proceedings of the 2023 CHI Conference on Human Factors in Computing Systems · doi:10.1145/3544548.3580919 · Cited by 366
“Cognitive load theory defines the demand that a situation or task places on a learner’s working memory [84] and is based in part on the learner’s prior knowledge and the complexity of the task or material [22].”
Izu, C., Schulte, C., Aggarwal, A., Cutts, Q., Duran, R., Gutica, M., Heinemann, B., Kraemer, E., Lonati, V., Mirolo, C., et al. (2019) · Proceedings of the Working Group Reports on Innovation and Technology in Computer Science Education · doi:10.1145/3344429.3372501 · Cited by 97
“Du-ran et al. [34], in particular, investigated how different program structures and plan-composition strategies could lead to students’ distinct perceptions of difficulty.”
BackgroundSelf-citationCognitive Load Theory in Computing Education Research: A Review
Duran, R., Zavgorodniaia, A., & Sorva, J. (2022) · ACM Transactions on Computing Education · doi:10.1145/3483843 · Cited by 92
“Another is the work of Duran et al. [18], who proposed (but did not empirically evaluate) an approach for analyzing the complexity of computer programs in terms of the hierarchical schemas required to understand the programs.”
BackgroundSelf-citationParsons Problems and Beyond: Systematic Literature Review and Empirical Study Designs
Ericson, B. J., Denny, P., Prather, J., Duran, R., Hellas, A., Leinonen, J., Miller, C. S., Morrison, B. B., Pearce, J. L., & Rodger, S. H. (2022) · Proceedings of the 2022 Working Group Reports on Innovation and Technology in Computer Science Education · doi:10.1145/3571785.3574127 · Cited by 56
“The difficulty of the material or task depends on the learner’s prior knowledge and the complexity of the task [49].”
BackgroundSelf-citationThrough (Tracking) Their Eyes: Abstraction and Complexity in Program Comprehension
Kather, P., Duran, R., & Vahrenhold, J. (2021) · ACM Transactions on Computing Education · doi:10.1145/3480171 · Cited by 34
“[15] to differentiate and evaluate the complexity and difficulty of comprehending programs (see the left part of Figure 1).”
BackgroundInfluentialSelf-citationTowards a Common Instrument for Measuring Prior Programming Knowledge
Duran, R., Rybicki, J.-M., Hellas, A., & Suoranta, S. (2019) · ACM Conference on Innovation and Technology in Computer Science Education (ITiCSE) · doi:10.1145/3304221.3319755 · Cited by 34
“The levels were designed using the principles of the stage of cognitive development in the programming context [9, 22, 32].”
BackgroundMethodInfluentialSelf-citationMalmi, L., Sheard, J., Kinnunen, P., Simon, N. P., & Sinclair, J. E. (2022) · ACM Transactions on Computing Education · doi:10.1145/3530221 · Cited by 32
“[38] address the challenge of evaluating how complex it is for students to comprehend program code: what aspects are involved and how they interact to increase the cognitive complexity when students are reading or tracing programs.”
BackgroundInfluentialExploring the Value of Student Self-Evaluation in Introductory Programming
Duran, R., Rybicki, J.-M., Sorva, J., & Hellas, A. (2019) · ACM Conference on International Computing Education Research (ICER) · doi:10.1145/3291279.3339407 · Cited by 30
“We introduce granularity to those levels by adding sub-levels of complexity as the number and quality of interacting elements [5, 14, 44] and students’ familiarity with the code.”
BackgroundSelf-citationDuran, R., Sorva, J., & Seppälä, O. (2021) · ACM Transactions on Computing Education · doi:10.1145/3469128 · Cited by 27
“To address this, Duran et al. [39] have proposed an extension to cognitive schema theory, characterizing each program’s complexity in terms of the hierarchical schemas that the programmer uses to reason about the program.”
BackgroundSelf-citationTecnologias na Educação em Computação: Primeiros Referenciais
Bispo, E. L., Raabe, A. L. A., Matos, E. D. S., Maschio, E., Barbosa, E. F., de Carvalho, L. S. G., Bittencourt, R. A., Duran, R., & Falcão, T. P. (2020) · Revista Brasileira de Informática na Educação · doi:10.5753/rbie.2020.28.0.509 · Cited by 24
Self-citationSo many brackets! an analysis of how SQL learners (mis)manage complexity during query formulation
Miedema, D., Fletcher, G., & Aivaloglou, E. (2022) · IEEE International Conference on Program Comprehension (ICPC) · doi:10.1145/3524610.3529158 · Cited by 23
“The effects of program complexity on comprehension and cognitive load have also been widely studied [7].”
BackgroundMethodEvaluating How Novices Utilize Debuggers and Code Execution to Understand Code
Hassan, M. R., Zeng, G., & Zilles, C. B. (2024) · ACM Conference on International Computing Education Research (ICER) · doi:10.1145/3632620.3671126 · Cited by 22
“[11].”
InfluentialUnraveling novices’ code composition difficulties
Weeda, R., Smetsers, S., & Barendsen, E. (2023) · Computer Science Education · doi:10.1080/08993408.2023.2169067 · Cited by 20
“During learning, in order to try to understand how programs are run, students may make a (simplified) model of a computer, described by (Du Boulay, 1986) as the ‘notional machine’ (Duran et al., 2018).”
InfluentialMeasuring the Cognitive Load of Learning to Program: A Replication Study
Zavgorodniaia, A., Duran, R., Hellas, A., Seppälä, O., & Sorva, J. (2020) · doi:10.1145/3416465.3416468 · Cited by 17
Self-citationMansoor, N., Peterson, C. S., Dodd, M. D., & Sharif, B. (2023) · ACM Transactions on Computing Education · doi:10.1145/3632530 · Cited by 12
“For future work, we plan to evaluate different program complexities [ 3 , 21 ] within each task category.”
BackgroundMethodClassification of strategies for solving programming problems using AoI sequence analysis
Obaidellah, U. H. B., Raschke, M., & Blascheck, T. (2019) · ACM Symposium on Eye Tracking Research and Applications (ETRA) · doi:10.1145/3314111.3319825 · Cited by 12
“Past research on schema theory in programming [Duran et al. 2018; Schulte et al. 2010; Soloway 1986] has investigated program construction and comprehension involved while participants solve programming problems.”
Aronshtam, L., Shrot, T., & Shmallo, R. (2021) · Education and Information Technologies · doi:10.1007/s10639-021-10532-0 · Cited by 12
“SOLO provides a general framework that can be applied to evaluate learning quality in different disciplines and for a wide range of tasks (e.g., Biggs & Collis, 1982; Chan et al., 2002; Duran et al., 2018; Fokides, 2017; Hattie & Purdie, 1998; Statter & Armoni, 2020; Uzumcu & Bay, 2020).”
BackgroundHow Plans Occur in Novices' Programs: A Method to Evaluate Program-Writing Skills
Costantini, U., Lonati, V., & Morpurgo, A. (2020) · ACM Technical Symposium on Computer Science Education (SIGCSE) · doi:10.1145/3328778.3366870 · Cited by 10
“A theoretical framework is proposed in [9] to define and measure the complexity of programs.”
BackgroundRöth, J., Baum, M., Eilerts, K., Hornung, G., & Trefzger, T. (2022) · Springer eBooks · doi:10.1007/978-3-662-66131-4 · Cited by 9
Is Algorithm Comprehension Different from Program Comprehension?
Kather, P., & Vahrenhold, J. (2021) · IEEE International Conference on Program Comprehension (ICPC) · doi:10.1109/icpc52881.2021.00053 · Cited by 9
Comparing estimates of difficulty of programming constructs
Bastian, M., & Mühling, A. (2022) · Koli Calling International Conference on Computing Education Research · doi:10.1145/3564721.3565950 · Cited by 8
“In contrast to complexity, the difficulty of a task additionally “depends on the characteristics of the person who engages in the task”[10].”
BackgroundMethodInfluentialToo Simple? Notions of Task Complexity used in Maintenance-based Studies of Programming Tools
Rein, P., Beckmann, T., Krebs, E., Mattis, T., & Hirschfeld, R. (2023) · IEEE International Conference on Program Comprehension (ICPC) · doi:10.1109/icpc58990.2023.00040 · Cited by 8
“21] control flow: CYCLO, cognitive complexity [42]–[44] architecture: closeness of mapping from domain to code [46], suitability of architecture for the patch [73, p.”
BackgroundProgramming Versus Natural Language: On the Effect of Context on Typing in CS1
Edwards, J., Leinonen, J., Birthare, C., Zavgorodniaia, A., & Hellas, A. (2020) · ACM Conference on International Computing Education Research (ICER) · doi:10.1145/3372782.3406272 · Cited by 8
“This could bring additional support to existing approaches for measuring cognitive load (e.g. [37]) and approaches for measuring complexity of computer programs (e.g. [11]).”
MethodCognitive Load Analyzer: A Support Tool for Cognitive-Driven Development
Pereira, J. H. A., de Souza, A. L. O. T., & Pinto, V. H. S. C. (2021) · Brazilian Symposium on Software Engineering · doi:10.1145/3474624.3476011 · Cited by 7
“Most research involving human cognition in software engineering focuses on evaluating programs and learning rather than on understanding how software development could be guided by this perspective [5].”
BackgroundImplementing Flipped Classroom Strategy in Learning Programming
Eusoff, R., Salleh, S. M., & Zın, A. M. (2021) · International Journal of Advanced Computer Science and Applications · doi:10.14569/ijacsa.2021.0121066 · Cited by 7
“Among the challenges in programming are high cognitive workload [1][8], inappropriate learning strategies, time constraints, and lack of preparation before entering the classroom [2][9].”
BackgroundSimplifying Programming for Non-technical Students: A Hermeneutic Approach
Valente, A., & Marchetti, E. (2022) · Künstliche Intell. · doi:10.1007/s13218-021-00748-0 · Cited by 6
“How can we define a NOM for multimedia programs in Python that is at a similar level of complexity as NOM 1 ? We want to follow [6] in our approach to compare complexity in relation to NOMs, therefore we propose to investigate this question by first defining two simple tasks involving images.”
BackgroundMethodInfluentialA Selective Review of Computing Education Research
Malmi, L., & Johri, A. (2023) · Routledge eBooks · doi:10.4324/9781003287483-31 · Cited by 6
PLAID: Supporting Computing Instructors to Identify Domain-Specific Programming Plans at Scale
Jain, Y., Demirtaş, M. A., & Cunningham, K. I. (2025) · CHI Conference on Human Factors in Computing Systems · doi:10.1145/3706598.3713832 · Cited by 4
“A variety of classroom instructional techniques have organized instruction around common patterns [12, 54, 55], used plans to inform the design of instruction [18], and evaluated students’ expertise based on their ability to recall plans [31].”
A Hermeneutic Approach to Simplify Programming: Secondary Education Case Studies
Valente, A., & Marchetti, E. (2022) · Lecture notes in computer science · doi:10.1007/978-3-031-05657-4_36 · Cited by 4
A visual notation for succinct program traces
Bajaj, D., Erwig, M., & Fedorin, D. (2023) · Journal of Computer Languages · doi:10.1016/j.cola.2023.101199 · Cited by 3
Cunningham, K. A. (2020) · Deep Blue (University of Michigan) · doi:10.7302/1339 · Cited by 3
Ferramentas de Visualização de Programas na Compreensão de Funções de Alta-Ordem
Martins, M. R., & Durán, R. (2023) · doi:10.5753/educomp_estendido.2023.229077 · Cited by 2
“C”ing the light – assessing code comprehension in novice programmers using C code patterns
Glasauer, C., Yeh, M. K. ‐., DeLong, L. A., Yu, Y., & Zhuang, Y. (2024) · Computer Science Education · doi:10.1080/08993408.2024.2317079 · Cited by 2
“We acknowledge that there are several approaches to decomposing programming code, e.g. Soloway’s (1986), Schulte’s Block Model (Schulte, 2008), or the model of hierarchical complexity (Commons et al., 1998; Duran et al., 2018).”
Computing-specific pedagogies and theoretical models: common uses and relationshipsPreprint
Malmi, L., Sheard, J., Szabo, C., & Kinnunen, P. (2024) · arXiv (Cornell University) · doi:10.48550/arxiv.2409.12245 · Cited by 2
Data-Informed Decision Making in Introductory Programming Instruction
Poitras, E., Durai, J. P. S., Raida, N. Z. Y., Sachdeva, J., Doucette, K., & Lin, M. P.-C. (2025) · IGI Global eBooks · doi:10.4018/979-8-3373-6960-0.ch009 · Cited by 1
Vasconcelos, H. M., Sousa, P. J. S. C. P., Silva, A., Dias, S., Pinto, J. P., van Golde, I., Tavares, P. J., & Moreira, P. M. G. J. (2026) · Procedia Structural Integrity · doi:10.1016/j.prostr.2026.01.076 · Cited by 1
Towards Methods for Identifying High-Quality Domain-Specific Programming Plans
Jain, Y., & Cunningham, K. I. (2023) · ACM Conference on International Computing Education Research (ICER) · doi:10.1145/3568812.3603478 · Cited by 1
“Based on our experience and analysis of prior work [6, 8], we propose threemetrics for the quality of a domain-specific programming plan.”
MethodTopic Difficulty in a Python Data Structures Course: Student Perceptions and Performance
Layman, L. M., Pence, T. B., & Narayan, S. (2025) · ACM Southeast Regional Conference (ACMSE) · doi:10.1145/3696673.3723056 · Cited by 1
Multilingual investigation of theory-based intervention for program comprehension
Ledesma, C. G. (2019) · University of Valladolid Documentary Repository (University of Valladolid)
Predicting programming assignment difficulty
Harju, E. (2019) · Helda - University of Helsinki Institutional Repository
Programming Techniques for Considering m Desired Conditions from n Possible Conditions
Riyana, S., Homdoung, N., & Sasujit, K. (2022) · Digital Technologies Research and Applications · doi:10.54963/dtra.v1i2.81
“Aside from software development and management techniques, data security ([27-29]), data privacy ([30-34]), and data complexity [35,36] must also be considered.”
MethodErste Schritte zur automatisierten Generation von Items in einem webbasierten Tracingsystem
Bastian, M., & Mühling, A. (2022) · Springer eBooks · doi:10.1007/978-3-662-66131-4_12
Applying the Mathematical Task Framework to K-8 Computing
Deutsch, M. (2023) · Workshop in Primary and Secondary Computing Education · doi:10.1145/3605468.3609753
“We might expect that programming-education taxonomies and frameworks such as SOLO [1, 7], Matrix [6], and CCCP [5] would help.”
MethodBarbieri, M., Amaral, J. V., & Duran, R. (2024) · Anais do Workshop sobre Educação em Computação (WEI) · doi:10.5753/wei.2024.2325
Self-citationHassan, M. R., & Zilles, C. B. (2024) · ACM Virtual Global Computing Education Conference (SIGCSE Virtual) · doi:10.1145/3649409.3691095
System for determining stages of development using music
Vasconcelos, J. H. M. (2022) · Portuguese National Funding Agency for Science, Research and Technology (RCAAP Project by FCT) · doi:10.34626/pt62-bj10
Kerr, O. (2024) · CLOK (University of Central Lancashire) · doi:10.17030/uclan.thesis.00052793
Weeda, R. (2025) · Radboud Repository (Radboud University)
Martins, M. R. (2024) · LA Referencia (Red Federada de Repositorios Institucionales de Publicaciones Científicas)
Towards a Code-Based Assessment of Computational Thinking Skills
Alpizar-Chacón, I., Monge-Fallas, J., Esquivel-Vargas, H., Trejos-Zelaya, I., González-Torres, A., & Sancho-Chavarría, L. (2026) · Applied Sciences · doi:10.3390/app16157400
Benites-Rodriguez, J., Benites-Angulo, L., Benites-Angulo, C., Tabacchi-Murillo, J., Rodriguez-Terrones, J., Amaro-Guzman, C., & Torres-Quiroz, A. (2026) · LACCEI International Multi-Conference for Engineering, Education and Technology (LACCEI) · doi:10.18687/laccei2026.1.1.2421
How (and How Not) Do Code Complexity Measures Predict Cognitive Load?
Thorgeirsson, S., & Vahrenhold, J. (2026) · ACM Conference on International Computing Education Research (ICER) · doi:10.1145/3765964.3811665
Martins, M. R., & Duran, R. (2026) · Anais do Workshop de Informática na Escola · doi:10.5753/wie.2026.27810
Self-citation
Metadata
- Authors
- Duran, R., Sorva, J., & Leite, S.
- Affiliations
- Aalto University (FI)
- Universidade do Porto (PT)
- Venue
- Proceedings of the 2018 ACM Conference on International Computing Education Research
- Publisher
- ACM
- Published
- 2018-08-08
- Pages
- 21-30
- OpenAlex
- W2885150285
- Cited by
- 44
- References
- 84
- Citations by year
- 2026: 4 · 2025: 3 · 2024: 4 · 2023: 9 · 2022: 10 · 2021: 6 · 2020: 4 · 2019: 4
- FWCI
- 3.96
- Type
- conference paper
- Language
- en
- Open access
- closed
- Locations
- ACM Conference on International Computing Education Research (ICER) (publishedVersion)
- Funders
- Conselho Nacional de Desenvolvimento Científico e Tecnológico (201365/2015-4)
- Topics
- Physical Sciences › Computer Science › Computer Science Applications › Teaching and Learning Programming
- Social Sciences › Psychology › Experimental and Cognitive Psychology › Visual and Cognitive Learning Processes
- Physical Sciences › Computer Science › Information Systems › Software Engineering Research
- Keywords
- software complexity, cognitive load theory, cognitive schemas, program composition, novice programmers
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
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.