title: Is it legal for the compiler to degrade the time complexity of a program? Is this considered observable behavior?
body: <p><sub>(<em>Note: This is intended to be a <a href="/questions/tagged/language-lawyer" class="post-tag" title="show questions tagged &#39;language-lawyer&#39;" rel="tag">language-lawyer</a> question; I'm not referring to any particular existing compilers.</em>)</sub></p>
  
  <p>When, if ever, is the compiler allowed to degrade the time complexity of a program?<br>
  Under what circumstances (if any) is this considered "observable behavior", and why?<br>
  (For example, can the compiler legally "reduce" a polynomial-time program to an exponential-time one?)</p>
  
  <p>If the answer differs in C and C++, or in different versions of either, then please explain the differences.</p>