Assessing the effectiveness of large language models for generating and estimating time complexity of code segments

Abstract

The time complexity of algorithms is a critical concept in computer science and engineering, and it is recognized as a fundamental topic in the Association for Computing Machinery (ACM) curricular recommendations. In alignment with these guidelines, numerous universities worldwide incorporate this topic into their introductory computer science courses, which typically have large student enrollments annually. Consequently, there is an increasing demand for automation in both instructional and assessment processes. This study explores the potential of Large Language Models (LLMs) to assist teaching staff in generating source code segments with predefined time complexity and determining the time complexity of given code segments, with applications in educational and examination contexts. We proposed a novel methodology for LLM evaluation in the aforementioned context and evaluated three prominent LLMs: ChatGPT, Gemini, and Llama, on their ability to generate and analyze C code segments exhibiting linear, logarithmic, quadratic, and exponential time complexities. A framework was developed to automate the prompt and segment generation and time complexity determination using two mainstream prompt engineering methods: zero-shot and chain-of-thought, and assessed the differences in code generation and time complexity analysis. A total of 960 generated segments were assessed on the correctness of time complexity, structural appropriateness, and suitability for exam use. The results suggest that ChatGPT is the most suitable LLM for generating segments with predefined time complexity (success rate goes up to 61%). All LLMs yielded the best results in generating linear segments, while exponential complexity posed the greatest challenge overall. A subset of generated segments was extracted to evaluate the time complexity determination capabilities. All three LLMs were asked to find the time complexity of each extracted segment. The most accurate LLM is ChatGPT (79.6%). We also assessed how good each LLM is in determining the time complexity of segments generated by itself. Llama outperforms others in that task (83% of successful determinations) when the zero-shot prompt method is used. The findings suggest that current LLMs cannot fully automate question generation and time complexity problem solving. However, they can substantially support the process and reduce the workload for educators.