>>>>> "BJörn" == BJörn Lindqvist <[EMAIL PROTECTED]> writes:
BJörn> On 2/5/07, [EMAIL PROTECTED] <[EMAIL PROTECTED]> 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 -- http://mail.python.org/mailman/listinfo/python-list