Чӣ гуна аст мураккабии вақти амали илова кардани унсур ба охири массиви навъи ArrayList?

Вақтли мураккаблик, ArrayList туридаги массивнинг охирига элемент қўшиш ўртача O(1) — амортизирланган доимий вақт.

Бу, чунки ArrayList элементларни белгиланган ўлчамдаги массивда сақлайди. Агар қўшишда ва массивда бўш жой бўлса, элемент одатда кейинги ўринга жойлаштирилади.

Аммо, агар массив тўлса, кенгайтириш амалиёти амалга оширилади — янги, катта ўлчамдаги массив яратилади ва барча элементлар унга кўчирилади. Бу операция O(n) вақт олади, бу ерда n — элементлар сони.

Масалан:

ArrayList<Integer> list = new ArrayList<>();
list.add(1); // O(1)
list.add(2); // O(1)
// Массивнинг ҳажми тўлганда, кенгайтириш — O(n)

Шунинг учун, қўшишнинг ўртача мураккаблиги — O(1), аммо энг ёмон ҳолатда — O(n).