On 2012-09-07, Oscar Benjamin <oscar.j.benja...@gmail.com> wrote: > On 2012-09-07, Steven D'Aprano <steve+comp.lang.pyt...@pearwood.info> wrote: >> <snip> > > Since string comparison is only useful if the strings can be equal or unequal, > the average case depends on how often they are equal/unequal as well as the > average complexity of both. For random strings the frequency of equal strings > decreases very fast as N increases so that the comparison of random strings is > O(1). > >> >> (I'm talking about the average here -- the actual number of comparisons >> can range all the way up to N, but the average is <= 2.) >> >> If I've done the maths right, the exact value for the average is: >> >> ((M-1)*sum( (N-i)*M**i for i in range(0, N) ) + N)/(M**N) > > I'm not sure where the extra N comes from --------^ but otherwise good.
Ok, I see it's for the case where they're equal. Oscar -- http://mail.python.org/mailman/listinfo/python-list
