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

Question

_{(Note: This is intended to be a language-lawyer question; I'm not referring to any particular existing compilers.)}

When, if ever, is the compiler allowed to degrade the time complexity of a program?
Under what circumstances (if any) is this considered "observable behavior", and why?
(For example, can the compiler legally "reduce" a polynomial-time program to an exponential-time one?)

If the answer differs in C and C++, or in different versions of either, then please explain the differences.

question from:https://stackoverflow.com/questions/26230791/is-it-legal-for-the-compiler-to-degrade-the-time-complexity-of-a-program-is-thi

Answer 1

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 (17.5.1.4 [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.