Какова временная сложность доступа к элементу в ArrayList по индексу?

Сложность — O(1).

Почему? ArrayList реализован на основе обычного массива. Доступ по индексу выполняется за константное время благодаря прямой адресации: array[index].

Пример:

ArrayList<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");

String element = list.get(1); // O(1) - мгновенный доступ ко второму элементу

Важное уточнение: Эта сложность относится только к доступу по индексу (get(index)). Поиск элемента по значению (indexOf(), contains()) имеет сложность O(n), так как требует последовательного перебора.