Home Original page

Abuse of Big Oh notation

Oscar Benjamin oscar.benjamin at bristol.ac.uk
Mon Aug 20 12:53:05 EDT 2012 
On 20 August 2012 17:01, Paul Rubin <no.email at nospam.invalid> wrote:

> Oscar Benjamin <oscar.j.benjamin at gmail.com> writes:
> > No it doen't. It is still O(k). The point of big O notation is to
> > understand the asymptotic behaviour of one variable as it becomes
> > large because of changes in other variables.
>
> Actually, two separate problems got mixed together late at night.  In
> neither case is k an independent variable that ranges over all possible
> values.  In both cases it is selected or observed by measurement (i.e.
> it is a dependent variable determined by something that is itself not
> independent).
>
> 1) Access in a rope: here, k is basically determined by the pointer size
> of the computer, which in CPython (the implementation we're discussing)
> the pointer size is 4 or 8 bytes (constants) in all instances AFAIK.  k
> should be a big enough that the pointer and allocation overhead is small
> compared to bloating the strings with UCS-2 or UCS-4, and small enough
> to not add much scan time.  It seems realistic to say k<=128 for this
> (several times smaller is probably fine).  128 is of course a constant
> and not a variable.  We are not concerned about hypothetical computers
> with billion bit pointers.
>

Okay, I see what you mean. If k is a hard-coded constant then it's not
unreasonable to say that O(k) is constant time in relation to the input
data (however big k is).

Oscar.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20120820/d542e3ec/attachment.html>
More information about the Python-list mailing list