Ποια είναι η χρονική πολυπλοκότητα της λειτουργίας προσθήκης ενός στοιχείου στο τέλος ενός πίνακα τύπου 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).