в (классическом) списке, чтобы обратиться к n-му элементу... потребуется проскакать от перводо элемента до нужного тебе... потому как нет прямых ссылок на нужный тебе элемент... каждый элемент содержит ссылку на следующий элемент... и поскольку эти нотации говорят о времени доступа для коллецкии вцелом (а не для отдельно взятого элемента), то и подразумевается самое большое количество шагов необходимых для доступа к нужному элементу... т. е., наихудший случай....
Я бы посоветовал почитать Кормена "Алгоритмы. Построение и анализ". Не говорю ее всю читать, просто там вначале описана вся эта теория с такой нотацией. О большое, Омега большое и т. д.
Это "big O notation", обозначение временно́й сложности алгоритма. Проще говоря, описывает то насколько быстр алгоритм. O - линейная зависимость времени выполнения от количества элементов. Обычно такая сложность у перебора всех элементов. O(1) - постоянное время выполнения (независимо от количества элементов). Обычно такая сложность у взятия элемента по его индексу.
допустим на доступ к элементу уходит 2 секунды, тогда если мы обратиться ко второму элементу пройдет 4 секунды. к 3му 6. к Nтэму элементу уйдет 2n секунд. это O. О (1) это значит что и к первому и к Nтэму элементу ты доберешься за 2 секунды. Это хватит для приблизительного понимая. Но это не совсем грамотное описание
если элементов будет в 1000 раз больше, то время доступа к списку увеличится в 1000 раз, а время доступа к массиву увеличится в 1 раз, т. е не изменится Не буквально, но суть такая