Help regarding knuth optimization.

Revision en2, by thegodfather, 2015-06-28 19:40:21

As part of this quora post(http://www.quora.com/What-is-Knuths-optimization-in-dynamic-programming) a description of knuth optimization has been given. It has been mentioned that :- it can be proven that mid[l,r-1] <= mid[l,r] <= mid[l+1,r] — this means monotonicity of mid by l and r. Can anyone one of you please help me regarding how to prove it?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English thegodfather 2015-06-28 19:40:56 4 Tiny change: 'n anyone one of you' -> 'n anyone of you'
en2 English thegodfather 2015-06-28 19:40:21 0 (published)
en1 English thegodfather 2015-06-28 19:39:54 389 Initial revision (saved to drafts)