The growth ffactor for the dynamic array depends on several factors including a space-time trade-off and algorithms used in the memory allocator itself. For growth factor ''a'', the average time per insertion operation is {{citation needed span|text=about ''a''/(''a''−1), while the number of wasted cells is bounded above by (''a''−1)''n''|date=January 2018}}. If memory allocator uses a [[First fit algorithm|first-fit allocation]] algorithm, then growth factor values such as ''a=2'' can cause dynamic array expansion to run out of memory even though a significant amount of memory may still be available.<ref name=":0">{{Cite web|title = C++ STL vector: definition, growth factor, member functions|url = http://www.gahcep.com/cpp-internals-stl-vector-part-1/|accessdate = 2015-08-05|archive-url = https://web.archive.org/web/20150806162750/http://www.gahcep.com/cpp-internals-stl-vector-part-1/|archive-date = 2015-08-06|url-status = dead}}</ref> There have been various discussions on ideal growth factor values, including proposals for the [[golden ratio]] as well as the value 1.5.<ref>{{Cite web|url = https://groups.google.com/forum/#!topic/comp.lang.c++.moderated/asH_VojWKJw%5B1-25%5D|title = vector growth factor of 1.5|date = |accessdate = |website = comp.lang.c++.moderated|publisher = Google Groups|last = |first = }}</ref> Many textbooks, however, use ''a'' = 2 for simplicity and analysis purposes.<ref name="gt-ad">{{citation|first1=Michael T.|last1=Goodrich|author1-link=Michael T. Goodrich|first2=Roberto|last2=Tamassia|author2-link=Roberto Tamassia|title=Algorithm Design: Foundations, Analysis and Internet Examples|publisher=Wiley|year=2002|contribution=1.5.2 Analyzing an Extendable Array Implementation|pages=39–41}}.</ref><ref name="clrs">{{Introduction to Algorithms|chapter=17.4 Dynamic tables|edition=2|pages=416–424}}</ref>
Below are growth factors used by several popular implementations:
Line 101:
== References ==
<references />
== External links ==
* [https://xlinux.nist.gov/dads/HTML/dynamicarray.html NIST Dictionary of Algorithms and Data Structures: Dynamic array]
* [http://www.bsdua.org/libbsdua.html#vpool VPOOL] - C language implementation of dynamic array.
* [https://web.archive.org/web/20090704095801/http://www.collectionspy.com/ CollectionSpy] — A Java profiler with explicit support for debugging ArrayList- and Vector-related issues.
* [http://opendatastructures.org/versions/edition-0.1e/ods-java/2_Array_Based_Lists.html Open Data Structures - Chapter 2 - Array-Based Lists], [[Pat Morin]]
