Comparing strings from the back?

[Oscar Benjamin]

On 2012-09-07, Oscar Benjamin <oscar.j.benjamin at gmail.com> wrote:
> On 2012-09-07, Steven D'Aprano <steve+comp.lang.python at 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