[EMAIL PROTECTED] writes: > >>>>> "Bart" == Bart Van Loon <[EMAIL PROTECTED]> writes: > > >> Such an operation will be O(N**2), > > Bart> why is that? > > The a[:] operation makes a copy of a (as will the x = a + [n] idiom).
I'm pretty confident append itself (and a+[n]) are linear in N=len(a) since the copying is linear and appending a single item in-place is constant time (OTOH calling append N times to construct a list or tree of length N from scratch is quadratic; I assume that is what you meant and also what the OP seems to want to use it for, so not doing it this way is sound advice). > Bart> I am building a binary tree where each node is a list. the two > Bart> children are the parent list + 1 and the parent list + 2. > > You might consider creating each node as > > left = [parent, 1] > right = [parent, 2] Or, if you don't need to mutate the tree ``left = (parent, 1)``. Tuples ought to have a little less memory overhead. 'as -- http://mail.python.org/mailman/listinfo/python-list
