Немного по программированию

Это "big O notation", обозначение временно́й сложности алгоритма. Проще говоря, описывает то насколько быстр алгоритм.
‎
O(n) - линейная зависимость времени выполнения от количества элементов. Обычно такая сложность у перебора всех элементов.
O(1) - постоянное время выполнения (независимо от количества элементов). Обычно такая сложность у взятия элемента по его индексу.

в (классическом) списке, чтобы обратиться к n-му элементу... потребуется проскакать от перводо элемента до нужного тебе...
потому как нет прямых ссылок на нужный тебе элемент... каждый элемент содержит ссылку на следующий элемент...
и поскольку эти нотации говорят о времени доступа для коллецкии вцелом (а не для отдельно взятого элемента), то и подразумевается самое большое количество шагов необходимых для доступа к нужному элементу... т. е., наихудший случай....

Я бы посоветовал почитать Кормена "Алгоритмы. Построение и анализ". Не говорю ее всю читать, просто там вначале описана вся эта теория с такой нотацией. О большое, Омега большое и т. д.

если элементов будет в 1000 раз больше, то время доступа к списку увеличится в 1000 раз, а время доступа к массиву увеличится в 1 раз, т. е не изменится
Не буквально, но суть такая

допустим на доступ к элементу уходит 2 секунды, тогда если мы обратиться ко второму элементу пройдет 4 секунды. к 3му 6. к Nтэму элементу уйдет 2n секунд. это O(n).
О (1) это значит что и к первому и к Nтэму элементу ты доберешься за 2 секунды. Это хватит для приблизительного понимая. Но это не совсем грамотное описание