Дар кадом ҳолатҳо илова кардани унсури охир ба ArrayList метавонад дорои мураккабии вақтии O(n) бошад?

Илова кардани унсур ба охири ArrayList одатан дорои мураккабии вақти O(1) аст, аммо дар баъзе ҳолатҳо метавонад O(n) бошад. Ин вақте рӯй медиҳад, ки массиви дохилӣ, ки унсурҳоро нигоҳ медорад, пур мешавад ва бояд васеъ карда шавад.

Ҳангоми илова кардани унсури нав:

• Агар ҷой бошад, унсур одатан илова мешавад — O(1).
• Агар ҷой набошад, массиви нав бо андозаи калонтар (одатан 1.5-2 маротиба калонтар) сохта мешавад, ва ҳамаи унсурҳои мавҷуда ба массиви нав нусхабардорӣ мешаванд — ин амалиёт O(n).

Аз ин рӯ, илова кардани унсур метавонад дар лаҳзаи васеъ кардани массиви дохилӣ, мураккабии вақти O(n) дошта бошад.