Kako odrediti vremenske troškove pri umetanju elementa u sredinu niza implementiranog putem ArrayList?

Вставка элемента в середину ArrayList требует сдвига всех элементов, стоящих после позиции вставки, на одну позицию вправо. Это означает, что временные затраты пропорциональны количеству таких элементов.

Если обозначить размер списка как N, а позицию вставки как k, то в худшем случае (вставка в начало) нужно сдвинуть почти все N элементов, что даёт временную сложность O(N). Вставка в конец — O(1), так как сдвиг не нужен.

Таким образом, вставка в середину массива через ArrayList имеет временную сложность порядка O(N - k), где k — индекс вставки.