Dinamik massiv ArrayListning boshiga element qo'shish operatsiyasining vaqt murakkabligi qanday?

Dinamik massivga (masalan, Java'da ArrayList) element qo'shish boshlanishiga vaqt murakkabligi O(n), bu yerda n massivdagi elementlar soni.

Bu shuni anglatadiki, boshlanishiga qo'shishda mavjud barcha elementlar o'ngga bir pozitsiya siljishi kerak, yangi element uchun joy bo'shatish uchun. Elementlarni nusxalash jarayoni chiziqli vaqt oladi.

Misol:

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

// Boshlanishiga qo'shish
list.add(0, 0); // barcha elementlarni o'ngga siljitadi

Shuning uchun, oxiriga qo'shish odatda tezroq (amortizatsiya qilingan O(1)), boshlanishiga esa — O(n).