On Monday 31 March 2008, Simon King wrote: > > So, this is much faster than sum, but it seems to me that it still > grows about linearly. > I remember having heard somewhere that summation of a list can be done > in logarithmic time. > But i am absolutely not sure if this is really true, and likely i am > mistaken. > Hence, sorry for my lack of "general computer science culture". > > Yours > Simon > That is true is you consider only the addition operations. In practice you have to fetch the operands from memory and in modern machines that tends to be the limiting factor. It's a while since I studied the technology in any depth, but for a good while it's been the case that a cpu can do the additions while it's waiting for the data to load from memory.
Bill -- +---------------------------------------+ | Bill Purvis, Amateur Mathematician | | email: [EMAIL PROTECTED] | | http://bil.members.beeb.net | +---------------------------------------+ --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
