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

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

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

Παράδειγμα:

• Εισαγωγή στο τέλος με διαθέσιμο χώρο: O(1)
• Εισαγωγή στην αρχή ή στη μέση: O(n) λόγω μετακίνησης των στοιχείων

Σε δυναμικούς πίνακες (π.χ., ArrayList στη Java), όταν ο πίνακας γεμίζει, γίνεται αντιγραφή σε έναν νέο πίνακα μεγαλύτερου μεγέθους, που επίσης απαιτεί χρόνο O(n).