Какая сложность поиска и вставки в ArrayList

Поиск: O(n) – линейный поиск, т.к. нужно перебрать элементы.
Вставка:

• В конец (add()): O(1) – амортизированная сложность (если capacity достаточно).
• В середину/начало (add(index, element)): O(n) – сдвиг элементов.

val list = ArrayList<Int>()
list.add(1) // O(1)
list.add(0, 2) // O(n) – сдвиг всех элементов
val index = list.indexOf(1) // O(n) – поиск

Примечание: Для частых вставок/удалений в середину лучше использовать LinkedList (O(1) вставка/удаление, но O(n) доступ по индексу).