# BigO(Bench): Can LLMs Generate Code with Controlled Time and Space Complexity?

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Mar 2025.

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

- [CWM: An Open-Weights LLM for Research on Code Generation with World Models](https://mlsanity.com/paper/2510.02387/) (2025)
- [GSO: Challenging Software Optimization Tasks for Evaluating SWE-Agents](https://mlsanity.com/paper/2505.23671/) (2025)
- [From Code Foundation Models to Agents and Applications: A Comprehensive Survey and Practical Guide to Code Intelligence](https://mlsanity.com/paper/2511.18538/) (2025)
- [AlgoSimBench: Identifying Algorithmically Similar Problems for Competitive Programming](https://mlsanity.com/paper/2507.15378/) (2025)
- [Extrapolative Weight Averaging Reveals Correctness-Efficiency Frontiers in Code RL](https://mlsanity.com/paper/2605.28751/) (2026)
- [SIMCOPILOT: Evaluating Large Language Models for Copilot-Style Code Generation](https://mlsanity.com/paper/2505.21514/) (2025)
- [LLM-Based Instance-Driven Heuristic Bias In the Context of a Biased Random Key Genetic Algorithm](https://mlsanity.com/paper/2509.09707/) (2025)
- [Rethinking Technology Stack Selection with AI Coding Proficiency](https://mlsanity.com/paper/2509.11132/) (2025)
- [SwiftSolve: A Self-Iterative, Complexity-Aware Multi-Agent Framework for Competitive Programming](https://mlsanity.com/paper/2510.22626/) (2025)
- [CodeGolf Bench: A Multi-Language Benchmark for Evaluating Concise Code Generation Capabilities of Large Language Models](https://mlsanity.com/paper/2605.30394/) (2026)
- [Towards Evaluation of Implicit Software World Models in Coding LLMs](https://mlsanity.com/paper/2606.27406/) (2026)
- [Memorization Diagnostics for Code LLMs Should be Scale-Aware](https://mlsanity.com/paper/2608.12771/) (2026)

## Abstract (arXiv)

We introduce BigO(Bench), a novel coding benchmark designed to evaluate the capabilities of generative language models in understanding and generating code with specified time and space complexities. This benchmark addresses the gap in current evaluations that often overlook the ability of models to comprehend and produce code constrained by computational complexity. BigO(Bench) includes tooling to infer the algorithmic complexity of any Python function from profiling measurements, including human- or LLM-generated solutions. BigO(Bench) also includes of set of 3,105 coding problems and 1,190,250 solutions from Code Contests annotated with inferred (synthetic) time and space complexity labels from the complexity framework, as well as corresponding runtime and memory footprint values for a large set of input sizes. We present results from evaluating multiple state-of-the-art language models on this benchmark, highlighting their strengths and weaknesses in handling complexity requirements. In particular, token-space reasoning models are unrivaled in code generation but not in complexity understanding, hinting that they may not generalize well to tasks for which no reward was given at training time.