Discovering Missing Stages in the Teaching of Algorithm Analysis: an APOS-based study

Students learn abstract concepts such as algorithm analysis in stages, progressively understanding the same concept at higher levels of abstraction. Without supporting students to progress to each stage, students will not achieve higher levels of understanding. With the aim of improving teaching of algorithm analysis, we analyzed teaching materials and assessments from two undergraduate Data Structures & Algorithms modules to investigate whether there are "missing" stages in the teaching of algorithm analysis on these modules, using APOS theory as a framework to model the learning stages of algorithm analysis concepts and the progressions between them. In our analysis, we identified five stages of learning the concepts of "growth function", "order of growth" and "time complexity", and found that the teaching delivered to students supported some but not all progressions between these stages. In line with APOS theory, we also make recommendations to improve teaching of algorithm analysis concepts by supporting progression to these missing stages.