In a non-volatile memory, a selected page on a word line is successively programmed by a series of voltage pulses of a staircase waveform with verifications in between the pulses until the page is verified to a designated pattern. The programming voltage at the time the page is programmed verified will be used to estimate the initial value of a starting programming voltage for the page. The estimation is further refined by using the estimate from a first pass in a second pass. Also, when the test is over multiple blocks, sampling of word lines based on similar geometrical locations of the blocks can yield a starting programming voltage optimized for faster programming pages.