Ποιος είναι ο χειρότερος χρόνος εκτέλεσης της μεθόδου add() για ArrayList;

Χρονικό διάστημα amortized σταθερό O(1).

Στις περισσότερες περιπτώσεις, το add() εκτελείται σε σταθερό χρόνο, καθώς το νέο στοιχείο απλώς προστίθεται στο τέλος του υπάρχοντος εσωτερικού πίνακα.

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

Ωστόσο, καθώς τέτοιες αλλαγές μεγέθους συμβαίνουν σπάνια και διανέμονται σε πολλές κλήσεις του add(), ο μέσος χρόνος εκτέλεσης του add() (αμortized) παραμένει σταθερός.