動的配列（例：C++のstd::vectorやPythonのlist）への要素追加（append）の計算量の振る舞いとして正しいものはどれか？

多くの動的配列実装は容量が足りないときに内部配列を倍増するなどの再配置を行います。個々の追加操作は再配置が発生するとO(n)のコストになりますが、再配置は頻繁に起きないため多数の追加操作に対して合計コストを平均化すると1操作あたりの平均コストは定数時間、つまりアモータイズド（平均的に）O(1)になります。これを理解すると、頻繁なappendがある場合でも通常は高速に動作します。