> > Nope, Ted. I asked for a O(log(n)) solution, not an O(n) one.
>
> I don't think that's possible with a numeric vector. Inserting an entry
> at a random location is an O(n) operation, since you need to move all
> following values out of the way.
If the vector is presorted, wouldn't a binary search find the correct location
in O(log(n))? (roughly log2(n)?)
After that any insertion depends on how fast R can move memory about so the
overall speed clearly depends on factors other than finding the location.
S Ellison
*******************************************************************
This email and any attachments are confidential. Any use...{{dropped:8}}
______________________________________________
R-help@r-project.org mailing list -- To UNSUBSCRIBE and more, see
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.
