# Learning based Methods for Code Runtime Complexity Prediction

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Nov 2019.

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

- [ECCO: Can We Improve Model-Generated Code Efficiency Without Sacrificing Functional Correctness?](https://mlsanity.com/paper/2407.14044/) (2024)
- [Benchmarking AI Models in Software Engineering: A Review, Search Tool, and Unified Approach for Elevating Benchmark Quality](https://mlsanity.com/paper/2503.05860/) (2025)
- [TASTY: A Transformer based Approach to Space and Time complexity](https://mlsanity.com/paper/2305.05379/) (2023)
- [TCProF: Time-Complexity Prediction SSL Framework](https://mlsanity.com/paper/2502.15749/) (2025)
- [MEC3O: Multi-Expert Consensus for Code Time Complexity Prediction](https://mlsanity.com/paper/2510.09049/) (2025)

## Abstract (arXiv)

Predicting the runtime complexity of a programming code is an arduous task. In fact, even for humans, it requires a subtle analysis and comprehensive knowledge of algorithms to predict time complexity with high fidelity, given any code. As per Turing's Halting problem proof, estimating code complexity is mathematically impossible. Nevertheless, an approximate solution to such a task can help developers to get real-time feedback for the efficiency of their code. In this work, we model this problem as a machine learning task and check its feasibility with thorough analysis. Due to the lack of any open source dataset for this task, we propose our own annotated dataset CoRCoD: Code Runtime Complexity Dataset, extracted from online judges. We establish baselines using two different approaches: feature engineering and code embeddings, to achieve state of the art results and compare their performances. Such solutions can be widely useful in potential applications like automatically grading coding assignments, IDE-integrated tools for static code analysis, and others.