In programming a non-volatile memory involving alternately applying a programming pulse and verifying the programming, time is saved in the program verify portion when, depending on the states of the memory cells, a portion of the verify operation is recognized to be superfluous and skipped. Preferably, in a program verify operation relative to a demarcation threshold level for demarcating between two memory states, the verify operation includes a sequence of two verify sub-cycles, the first sub-cycle performing a verify relative to a first threshold level at a predetermined margin below the demarcation threshold level and the second sub-cycle performing a verify relative to a second threshold level which is identical to the demarcation threshold level. Unlike conventional cases, the second sub-cycle is not performed until any one memory cell of the group has been verified to pass the first threshold.