რის შემთხვევებში დამატება ელემენტი ArrayList-ის ბოლოს შეიძლება ჰქონდეს დროის სირთულე O(n)?

ArrayList-ის ბოლო ნაწილში ელემენტის დამატება ჩვეულებრივ აქვს ამორტიზებული დროის სირთულე O(1), მაგრამ ზოგიერთ შემთხვევაში შეიძლება იყოს O(n). ეს ხდება მაშინ, როდესაც შიდა მასივი, რომელიც ინახავს ელემენტებს, სავსეა და მისი გაფართოება სჭირდება.

ახალი ელემენტის დამატებისას:

• თუ ადგილი არის, ელემენტი უბრალოდ ემატება — O(1).
• თუ ადგილი არ არის, ქმნიან ახალ მასივს უფრო დიდ ზომაში (საშუალოდ 1.5-2 ჯერ მეტი), და ყველა არსებული ელემენტი გადადის ახალ მასივში — ეს ოპერაციაა O(n).

ამიტომ, ელემენტის დამატება შეიძლება იყოს დროის სირთულე O(n) სწორედ იმ დროს, როდესაც შიდა მასივი გაფართოვდება.