Dynamic array: Difference between revisions

Revision as of 10:28, 23 September 2006

Revision as of 19:15, 24 September 2006

Line 40:

== Analysis ==

[[Image:Example.jpg]]<math>Insert formula here</math>

== == rr4 == ==

In choosing the percentage by which to enlarge the table, there is a time-space tradeoff: the average time per insertion operation is about ''a''/(''a''&minus;1), where ''a'' is the multiplier factor such as 2 by which the table size increases each time. On the other hand, ''capacity'' minus ''size'' space is allocated but not in use, a quantity bounded above by (''a''&minus;1)''n''. The choice ''a''=2 is a commonly-used value, but depending on the application many values between about ''a''=1.2 and ''a''=4 may be suitable.