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

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

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

Επομένως, η εισαγωγή στο μέσο ενός πίνακα μέσω ArrayList έχει μια χρονική πολυπλοκότητα της τάξης O(N - k), όπου k είναι ο δείκτης εισαγωγής.