On 20 August 2012 17:01, Paul Rubin <no.email@nospam.invalid> wrote: > Oscar Benjamin <oscar.j.benja...@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.
-- http://mail.python.org/mailman/listinfo/python-list
