title: An Example for Non-Monotone Worst-Case Complexity
body: <p>Is somebody aware of a natural program or algorithm that has a non-monotone worst-case behavior?</p>
  
  <p>By non-monotone worst-case behavior I mean that there is a natural number n such that the worst-case runtime for inputs of size n+1 is less than the worst-case runtime for inputs of size n.</p>
  
  <p>Of course, it is easy to construct a program with this behavior.  It might even be the case that this happens for small n (like n = 1) in natural programs.  But I'm interested in a useful algorithm that is non-monotone for large n.</p>