title: Efficiency of purely functional programming
body: <p>Does anyone know what is the worst possible asymptotic slowdown that can happen when programming purely functionally as opposed to imperatively (i.e. allowing side-effects)?</p>
  
  <p><em>Clarification from comment by itowlson</em>: is there any problem for which the best known non-destructive algorithm is asymptotically worse than the best known destructive algorithm, and if so by how much?</p>