in place-ness of list.append

[skip at pobox.com]

>>>>> "BJörn" == BJörn Lindqvist <bjourne at gmail.com> writes:

    BJörn> On 2/5/07, skip at pobox.com <skip at pobox.com> wrote:
    >> 
    Bart> #--------------------------------------------------
    Bart> def addnumber(alist, num):
    Bart> """ work around the inplace-ness of .append """
    Bart> mylist = alist[:]
    Bart> mylist.append(num)
    Bart> return mylist
    Bart> #--------------------------------------------------
    >> 
    >> Such an operation will be O(N**2), and thus expensive if performed
    >> frequently on lists of moderate length.  I've never been tempted to
    >> do this.

    BJörn> How can that be? Making a copy of a list is O(N), isn't it?

Yes, not enough sleep under my belt or caffeine in my system (*) when I
wrote those replies.  addnumber is O(N).  If you are building a binary tree
of M elements you're going to wind up with an O(N*M) or O(N**2) cost to
build the tree though.  Actually, I think in the case of building the binary
tree you wind up with an O(N*log N) algorithm since you don't have to
traverse the entire set of nodes you've already built to find where to
insert the next one.

Skip

(*) It really sucks when someone's car alarm goes off at 4AM with no visual
indication when it's about -5F outside and you have to actually go outside
to check and make sure it's not your car (only to find out it's the car
directly behind yours)...

S