<div class="gmail_quote">On 20 August 2012 17:01, Paul Rubin <span dir="ltr"><<a href="mailto:no.email@nospam.invalid" target="_blank">no.email@nospam.invalid</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div class="im">Oscar Benjamin <<a href="mailto:oscar.j.benjamin@gmail.com">oscar.j.benjamin@gmail.com</a>> writes:<br>
> No it doen't. It is still O(k). The point of big O notation is to<br>
> understand the asymptotic behaviour of one variable as it becomes<br>
> large because of changes in other variables.<br>
<br>
</div>Actually, two separate problems got mixed together late at night.  In<br>
neither case is k an independent variable that ranges over all possible<br>
values.  In both cases it is selected or observed by measurement (i.e.<br>
it is a dependent variable determined by something that is itself not<br>
independent).<br>
<br>
1) Access in a rope: here, k is basically determined by the pointer size<br>
of the computer, which in CPython (the implementation we're discussing)<br>
the pointer size is 4 or 8 bytes (constants) in all instances AFAIK.  k<br>
should be a big enough that the pointer and allocation overhead is small<br>
compared to bloating the strings with UCS-2 or UCS-4, and small enough<br>
to not add much scan time.  It seems realistic to say k<=128 for this<br>
(several times smaller is probably fine).  128 is of course a constant<br>
and not a variable.  We are not concerned about hypothetical computers<br>
with billion bit pointers.<br></blockquote><div><br></div><div>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).</div>
<div><br></div><div>Oscar.</div></div>