Σε ποιες περιπτώσεις η προσθήκη ενός στοιχείου στο τέλος ενός ArrayList μπορεί να έχει χρονική πολυπλοκότητα O(n);

Η προσθήκη ενός στοιχείου στο τέλος ενός ArrayList έχει γενικά μια αθροιστική χρονική πολυπλοκότητα O(1), αλλά σε ορισμένες περιπτώσεις μπορεί να είναι O(n). Αυτό συμβαίνει όταν ο εσωτερικός πίνακας που αποθηκεύει τα στοιχεία είναι γεμάτος και χρειάζεται επέκταση.

Κατά την προσθήκη ενός νέου στοιχείου:

• Αν υπάρχει χώρος, το στοιχείο προστίθεται απλά — O(1).
• Αν δεν υπάρχει χώρος, δημιουργείται ένας νέος πίνακας μεγαλύτερου μεγέθους (συνήθως 1,5-2 φορές μεγαλύτερος), και όλα τα υπάρχοντα στοιχεία αντιγράφονται στον νέο πίνακα — αυτή η λειτουργία είναι O(n).

Επομένως, η προσθήκη ενός στοιχείου μπορεί να έχει χρονική πολυπλοκότητα O(n) ακριβώς τη στιγμή της επέκτασης του εσωτερικού πίνακα.