Knuth's improvement uses: . The left bound says: if was optimal for , then for you won't do better with any .
Expanding the interval rightward makes later splits more attractive, not earlier ones. The right bound says: if was optimal for , then for you won't do better with any . Adding an element on the left makes earlier splits more attractive. Both follow from QI by the same logic as the monotonicity proof. The bounds shrink your search range dramatically.