Abuse of Big Oh notation [was Re: How do I display unicode value stored in a string variable using ord()]

[Steven D'Aprano]

On Sun, 19 Aug 2012 10:48:06 -0700, Paul Rubin wrote:

> Terry Reedy <tjreedy at udel.edu> writes:

>> I would call it O(k), where k is a selectable constant. Slowing access
>> by a factor of 100 is hardly acceptable to me.
> 
> If k is constant then O(k) is the same as O(1).  That is how O notation
> works.

You might as well say that if N is constant, O(N**2) is constant too and 
just like magic you have now made Bubble Sort a constant-time sort 
function!

That's not how it works.

Of course *if* k is constant, O(k) is constant too, but k is not 
constant. In context we are talking about string indexing and slicing. 
There is no value of k, say, k = 2, for which you can say "People will 
sometimes ask for string[2] but never ask for string[3]". That is absurd.

Since k can vary from 0 to N-1, we can say that the average string index 
lookup is k = (N-1)//2 which clearly depends on N.


-- 
Steven