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

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

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

Παράδειγμα:

ArrayList<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);

// Εισαγωγή στην αρχή
list.add(0, 0); // μετακινεί όλα τα στοιχεία προς τα δεξιά

Έτσι, η εισαγωγή στο τέλος είναι συνήθως πιο γρήγορη (αμortized O(1)), ενώ στην αρχή είναι O(n).