On Nov 7, 5:05 pm, sturlamolden <sturlamol...@yahoo.no> wrote: > On 7 Nov, 03:46, gil_johnson <gil_john...@earthlink.net> wrote:> > > > I don't have the code with me, but for huge arrays, I have used > > something like: > > > >>> arr[0] = initializer > > >>> for i in range N: > > >>> arr.extend(arr) > > > This doubles the array every time through the loop, and you can add > > the powers of 2 to get the desired result. > > Gil > > You should really use append instead of extend. The above code is O > (N**2), with append it becomes O(N) on average.
I think the top one is O(N log N), and I'm suspicious that it's even possible to grow a list in less than O(N log N) time without knowing the final size in advance. Citation? Futhermore why would it matter to use extend instead of append; I'd assume extend uses the same growth algorithm. (Although in this case since the extend doubles the size of the list it most likely reallocates after each call.) [None]*N is linear time and is better than growing the list using append or extend. Carl Banks -- http://mail.python.org/mailman/listinfo/python-list
