but adds that "the system is so natural, that it very likely may have been conceived independently by others either before or since that time". Another early publication of this method was by Soviet researcher Andrey Ershov, in 1958. The first theoretical analysis of linear probing, showing that it takes constant expected time per operation with random hash functions, was given by Knuth. Sedgewick calls Knuth's work "a landmark in the analysis of algorithms". Significant later developments include a more detailed analysis of the probability distribution of the running time, and the proof that linear probing runs in constant time per operation with practically usable hash functions rather than with the idealized random functions assumed by earlier analysis. References Search algorithms Hashing