Is it legal for the compiler to degrade the time complexity of a program? Is this considered observable behavior?

The C standard doesn’t actually have a time complexity model, neither for its primitive operations, nor its library functions, so compilers are allowed to do pretty much anything that preserves program semantics (observable behavior).

The C++ standard only gives complexity guarantees only for some its library functions, and says ( [structure.specifications]):

Complexity requirements specified in the library clauses are upper bounds, and implementations that provide better complexity guarantees satisfy the requirements.

A compiler better preserve these bounds (and since many of the functions are templated/may be inlined, the compiler is involved), but the bounds are in terms of the number of elements in containers and restrict the number of calls to comparison operators and the like. Otherwise, the compiler is again free to do as it pleases.

Leave a Comment