Como é determinada a complexidade de acesso a um elemento por índice em ArrayList?

В ArrayList доступ к элементу по индексу имеет сложность O(1), то есть константное время. Это связано с тем, что ArrayList реализован на основе массива, где элементы хранятся в непрерывной области памяти.

Поэтому, чтобы получить элемент по индексу, достаточно вычислить адрес элемента как базовый адрес массива плюс смещение, что занимает фиксированное время независимо от размера списка.