# CodeComplex: Dataset for Worst-Case Time Complexity Prediction

arXiv: https://arxiv.org/abs/2401.08719 · HTML: https://mlsanity.com/paper/2401.08719/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Placed in Reasoning for agents, planning and code, one of 17 directions in LLM reasoning.
- First posted on arXiv 16 Jan 2024.

## Placed in

- LLM reasoning / [Reasoning for agents, planning and code](https://mlsanity.com/lr/reasoning-for-agents-planning-and-code/)

## Built on by (most cited first, 3 of 3)

- [MEC3O: Multi-Expert Consensus for Code Time Complexity Prediction](https://mlsanity.com/paper/2510.09049/) (2025)
- [Exploring Heterogeneous Model Merging Approach for Complex Knowledge Transfer](https://mlsanity.com/paper/2609.39369/) (2026)
- [CodeWalk: Generating Coding Benchmarks by Walking a Problem Graph](https://mlsanity.com/paper/2610.15345/) (2026)

## Abstract (arXiv)

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 various intricate factors such as the input range of variables and conditional loops. Current benchmarks fall short of providing a rigorous assessment due to limited data, language constraints, and insufficient labeling. They do not consider time complexity based on input representation and merely evaluate whether predictions fall into the same class, lacking a measure of how close incorrect predictions are to the correct ones. To address these dependencies, we introduce CodeComplex, the first robust and extensive dataset designed to evaluate LLMs' reasoning abilities in predicting code time complexity. CodeComplex comprises 4,900 Java codes and an equivalent number of Python codes, overcoming language and labeling constraints, carefully annotated with complexity labels based on input characteristics by a panel of algorithmic experts. Additionally, we propose specialized evaluation metrics for the reasoning of complexity prediction tasks, offering a more precise and reliable assessment of LLMs' reasoning capabilities. We release our dataset (https://github.com/sybaik1/CodeComplex-Data) and baseline models (https://github.com/sybaik1/CodeComplex-Models) publicly to encourage the relevant (NLP, SE, and PL) communities to utilize and participate in this research.