Πώς καθορίζεται η χρονική πολυπλοκότητα κατά την προσθήκη ενός στοιχείου σε ArrayList;

Η χρονική πολυπλοκότητα της προσθήκης ενός στοιχείου σε ArrayList είναι συνήθως αθροιστικά O(1). Αυτό οφείλεται στο ότι:

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

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

Παράδειγμα:

ArrayList<Integer> list = new ArrayList<>();
list.add(10); // Αθροιστικά O(1)