@article{Chen2026, 
author = {Li-Guo Chen and Xin Wang and Jue-Yu Chen and Ren-Zhao Liang and Zheng-Ran Zeng and Yang-Ning Li and Ying-Hui Li and Yi-Dong Wang and Yi-Jiang Xu and Qing Gao and Shi-Kun Zhang},
title = {Complexity-Constraint Code Evaluation: A Benchmark for Time Complexity Compliance in LLM-Generated Code},
year = {2026},
journal = {Journal of Computer Science and Technology},
volume = {41},
number = {3},
pages = {910-923},
keywords = {large language model for code (Code LLM), code evaluation, benchmark dataset, time complexity constraint},
url = {https://www.sciopen.com/article/10.1007/s11390-025-5518-5},
doi = {10.1007/s11390-025-5518-5},
abstract = {While large language models for code (Code LLMs) excel at generating functionally correct code, existing benchmarks neglect a crucial aspect: adherence to explicit time complexity constraints. We introduce the Complexity-Constraint Code Evaluation (C3E), a novel benchmark evaluating both functional correctness and complexity compliance across feasible and infeasible scenarios. C3E enables precise differentiation between asymptotic complexity classes and tests model robustness against theoretically impossible constraints. Our proposed Complexity Alignment Score (CAS) integrates correctness and complexity adherence into a unified metric, assessed through theoretical analysis rather than costly executions. Experiments reveal a striking gap in state-of-the-art models: GPT-4o achieves 81% correctness but only 31% CAS, demonstrating poor complexity compliance. Notably, most models fail to recognize infeasible constraints except advanced ones such as GPT-4o. These findings underscore the necessity for complexity-aware evaluation, positioning C3E as an essential tool for advancing real-world coding reliability in Code LLMs. The C3E benchmark is available at https://github.com/wahaha12321/C3E.}
}