C ode C omplex: Dataset for Worst-Case Time Complexity Prediction (2025)

Abstract: Reasoning ability of large language models (LLMs) is a crucial ability,especially in complex decision-making tasks. One significant task to show LLMs’reasoning capability is code time complexity prediction, which involves variousintricate factors such as the input range of variables and conditional loops.Current benchmarks fall short of providing a rigorous assessment due to limiteddata, language constraints, and insufficient labeling. They do not consider timecomplexity based on input representation and merely evaluate whether predictionsfall into the same class, lacking a measure of how close incorrect predictionsare to the correct ones.To address these dependencies, we introduce CodeComplex, the first robust andextensive dataset designed to evaluate LLMs’ reasoning abilities in predictingcode time complexity. CodeComplex comprises 4,900 Java codes and an equivalentnumber of Python codes, overcoming language and labeling constraints, carefullyannotated with complexity labels based on input characteristics by a panel ofalgorithmic experts. Additionally, we propose specialized evaluation metrics forthe reasoning of complexity prediction tasks, offering a more precise andreliable assessment of LLMs’ reasoning capabilities. We release our dataset andbaseline models publicly to encourage the relevant (NLP, SE, and PL) communitiesto utilize and participate in this research. Our code and data are available athttps://github.com/sybaik1/CodeComplex.

## introduction large language models (llms) demonstrate significant potential in complex decision-making tasks, with their inference capabilities being particularly valuable in software development @xcite . to further test llm's inferencing abilities, we showcase this domain of predicting the code time complexity, which requires * corresponding author. the consideration of numerous intricate factors. for example, factors such as algorithmic structure @xcite , data input size, and resource constraints can all influence the time complexity of code @xcite . understanding and optimizing these factors is crucial for improving the performance of complex algorithms and generating efficient code @xcite . despite the existence of benchmarks for the time complexity analysis, such as corcod @xcite , and tasty @xcite , these benchmarks have limitations on their current state. notably, corcod is the only publicly available dataset that is small in size, and while tasty considers both time and space complexity, its dataset remains undisclosed. consequently, there is a clear need for a comprehensive and publicly accessible benchmark that addresses these shortcomings. our work aims to fill this gap by introducing codecomplex, a dataset designed to be the definitive benchmark for evaluating llms' time complexity inference abilities. codecomplex offers several distinct advantages over existing benchmarks. first, it provides a larger and more diverse dataset, encompassing a broad range of programming languages beyond the limited scope of cor-cod, which focuses solely on java. second, our dataset encompasses a more comprehensive set of labeled complexity classes that cover general-use problem-solving algorithms, enabling a more detailed analysis. thirdly, codecomplex considers the representation of input data, distinguishing between numeric values and input size indicators, which is critical for accurate complexity analysis. lastly, we suggest detailed metrics that allow for a more nuanced assessment of llms' performance, moving beyond simple class-based evaluations. in summary, our contributions are as follows: through these contributions, codecomplex aims to advance the study of llms inference capabilities with the task of predicting code time complexity, ultimately fostering the development of optimized software. our benchmark sets a new standard for the evaluation of llms, providing a robust and comprehensive tool for researchers and practitioners alike. ## related work the llms have led to numerous advances in the field of natural language processing @xcite . therefore, recent research is ongoing to improve the reasoning ability of llms. numerous prompt engineering techniques emerged, such as zero-shot, few-shot, chain of thought, and prompt changing @xcite @xcite . specifically, the chain of thought prompting was proposed to encourage them to engage in inferential thinking, with the subsequent application of arithmetic, commonsense, and sentiment reasoning. the methodologies demonstrated that when the llms' reasoning was improved, their capability to perform a range of tasks was enhanced. nevertheless, it is evident that llms are still constrained in their capacity to reason about complex tasks. the enhancement of llm's capacity to reason effectively in complex domains is highly dependent upon the availability of a domain-specific and sophisticated dataset. in the field of code time complexity, some representative complex tasks have been proposed as a method for improving the reasoning ability of llm models. recently, sikka et al. (2020) explored code complexity prediction using machine learning-based methods. they curated the corcod dataset comprising 929 annotated java codes. these codes were enriched with various hand-engineered features extracted from the code, encompassing counts of loops, methods, variables, jumps, breaks, switches, and the identification of specific data structures or algorithms like priority queues, hash maps, hash sets, and sorting functions. employing machine learning classification algorithms such as k-means, random forest, decision tree, svm, and more, they made predictions based on these diverse features. additionally, they explored graph2vec @xcite , a neural graph embedding framework that operates on a program's ast and achieves comparable performance results. another exploration by prenner and robbes (2021) scrutinized the potential of pre-trained programming language understanding models, particularly @xcite , for predicting code complexity. their experiments showcased promising results, suggesting that pre-trained models could serve as a viable solution in this domain. in the most recent development, @xcite tackled the analysis of time and space complexity using language models. they leveraged codes sourced from geeksforgeeks foot_0 and corcod, alongside a dataset comprising 3,803 java codes. their work showcased the viability of fine-tuning pre-trained language models such as graphcode-bert @xcite for predicting both time and space complexity, thereby opening new avenues for exploration in this field. ## the codecomplex dataset the codecomplex dataset contains a collection of codes written in two languages, java and python, from a competitive programming platform. our dataset originates from codeforces and collects data from codecontests @xcite , a competitive programming dataset tailored for machine learning applications created by deepmind. it comprises 9,800 codes, evenly split between java and python, with 4,900 codes each. we have categorized these codes into seven distinct complexity classes: constant (o(1)), linear (o(n)), quadratic (o(n 2 )), cubic (o(n 3 )), logarithmic (o(ln n), o(n ln n)), and exponential. each class contains a minimum of 500 java and python codes. we annotated all 9,800 codes with experts, which include the 317 java codes in the corcod dataset from codeforces. it is worth mentioning that the corcod, a previous dataset used for code complexity prediction, categorizes java codes into five complexity classes: o(1), o(n), o(n 2 ), o(ln n), and o(n ln n). however, it suffers from imbalanced class distribution, evident in ## experiments as a preliminary study on code complexity prediction using a large-scale dataset, we conduct experiments with well-known machine learningbased solutions and llms. first, we try to replicate the result by sikka et al. (2020) by employing traditional models such as decision tree (dt), random forest (rf), and support vector machine (svm). second, we use pre-trained programming language models (plms) such as codebert ( feng et al., 2020) ## results & analysis we present some selected interesting experimental results and analysis for various scenarios in the following section. full experimental results can be found in the appendix c due to the lack of space. ## conclusions we have presented codecomplex, the first largescale, bilingual benchmark dataset designed to rigorously assess the reasoning abilities of llms in predicting the worst-case time complexity of programs. by providing a comprehensive and balanced collection of java and python codes, along with input-aware annotations and a novel hierarchy complexity score (hc-score), our work establishes a more nuanced foundation for evaluating model performance beyond simple accuracy. our experiments with a wide range of models, from classical machine learning approaches to state-of-the-art llms, demonstrate that while current techniques show promise, a significant gap remains in achieving reliable performance for practical use cases, underscoring the need for continued research. looking ahead, we identify several key directions for future work to build upon this foundation. first, exploring more advanced prompting techniques is crucial. leveraging methods like chain-of-thought prompting could elicit stronger zero-shot reasoning, moving models from pattern matching to more deliberate, step-by-step analysis. second, to ensure models develop true algorithmic understanding, we propose conducting code obfuscation tests. assessing performance on functionally identical but syntactically varied or intentionally complex code would test the robustness of models beyond familiar, memorized patterns. third, the task itself can be evolved from classification to generation. future work should investigate open-ended complexity generation, where models produce a symbolic expression (e.g., o(n √ m)) rather than selecting from a fixed set of classes. this would represent a far more sophisticated level of reasoning. finally, the ability of models trained on codecomplex to generalize is paramount. we suggest conducting transfer experiments by evaluating these models on other benchmarks, such as corcod and problems from platforms like geeks-forgeeks, to measure out-of-domain performance gains and pave the way for more universally applicable code reasoners. pursuing these directions will be essential in developing llms with the sophisticated and reliable inference capabilities required for the next generation of software development tools.