A Java ArrayList равно O (n), если вы добавляете в начало, потому что System.arraycopy() линейно. При создании ArrayList в C я бы использовал realloc, чтобы перераспределить массив, когда он заполнится. Является ли realloc линейным?
ArrayList в java - это просто массив c динамического типа. System.arraycopy линейно. Это я точно знаю. Я думаю, что он копирует входной массив в выходной массив элемент за элементом.
Линейная временная сложность: время, необходимое для выполнения задачи, пропорционально количеству входных данных. Таким образом, копирование массива элемент за элементом является линейным, потому что для завершения sh требуется больше времени, чем больше массив.