Ποια είναι η χρονική πολυπλοκότητα της λειτουργίας προσθήκης ενός στοιχείου σε μια δυναμική λίστα;

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

Εξήγηση:

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

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

Παράδειγμα σε Go με slices:

var arr []int
arr = append(arr, 10) // προσθήκη στοιχείου

Το append θα επεκτείνει αυτόματα το slice αν χρειάζεται.