Improving code while preserving its functionality is a common task in the hi-tech industry. Yet students have difficulties improving an algorithm's run-time complexity by an order of magnitude. The paper focuses on assessing students' abilities in this area. We designed a Structure of the Observed Learning Outcome (SOLO) taxonomy, using software quality factors, to assess students' cognitive ability while improving complexity. The research was conducted with college students studying for their bachelor's degree in engineering. We established a classification based on their solutions for a given task. Later, we used the same task to validate our classification with another group of engineering students. We then compared the previous average grades of the second group of students with their SOLO levels. The results show that the higher the students' previous average grades, the greater the probability that their solutions would be classified at higher taxonomic levels. These results indicate that our SOLO classification is indeed accurate. The paper presents our novel SOLO taxonomic levels for tasks improving run-time complexity and offers several suggestions to assist students and enhance the teaching process.