From: Peter Suk Date: 2005-04-23T13:02:39+09:00 Subject: Re: Question: Time efficiency of Array << On Apr 22, 2005, at 9:48 PM, Saynatkari wrote: > I think it is a bit of a stretch to call the following test > 'real-world' :) That being said, Array does perform well. > > Remember that an rb-tree is O(log n) for insertion, deletion > _and_ search, and it can be treated as sparse. The key here is "real world." Array's trick of doubling its allocation gives us an "Amortized" time of O(2n) = O(n) which beats n insertions into a structure like a Binary Tree, which is O(n*log n). One of the handful of truly useful things I learned from Algorithms. A good summary for the Array trick: http://www.eli.sdsu.edu/courses/fall96/cs660/notes/amortizedAnalysis/ amortizedAnalysis.html Some more: http://www.cs.duke.edu/~mlittman/courses/Archive/cps130-97/lectures/ lect10/node14.html You can think of it as the "reverse Zeno's paradox." 1 + 2 + 4 + 8 + .... 2^0 + 2^1 + 2^2 + 2^3 + ... + 2^(n-1) = 2^n - 1 Or visually: X XX XXXX XXXXXXXX XXXXXXXXXXXXXXXX You'll always be able to stack the smaller levels into the missing space on the next to the last level and still have 1 empty space left over. So, Ruby's Array = Smalltalk's OrderedCollection. --Peter -- There's neither heaven nor hell, save what we grant ourselves. There's neither fairness nor justice, save what we grant each other.