Вы, наверное, не раз сталкивались с таким понятием как сложность алгоритмов. Существует несколько нотаций, которыми можно описать сложность алгоритма, в основном используется О-нотация (или О-большое), т.к. она описывает верхнюю границу сложности алгоритма в зависимости от входных параметров. Например, у вас есть такой метод:
int Method(int n) {
var sum = 0;
for (int i = 0; i < n; ++i) {
sum += i;
}
return sum;
} Т.е. мы передаем в метод некое число n, которое обозначает количество итераций цикла внутри метода. Верхняя сложность такого алгоритма будет O(n). При этом если мы добавим в конец метода еще несколько строк:
for (int i = 0; i < 10; ++i) {
sum += i;
}то казалось бы, что сложность должна увеличиться на 10 (O(n + 10), но в О-нотации это будет константное время, а значит мы не будем учитывать это в сложности, т.е. сложность все еще останется O(n).
Поэтому нужно понимать, что алгоритм с О-нотацией O(1) (константное время) может на самом деле занимать гораздо больше времени, чем вы расчитываете, это лишь показывает общую сложность алгоритма, но не говорит о его количестве операций.
Вот для сравнения методы со сложностью O(n) и O(1).
Метод O(n):
int Method(int n) {
var sum = 0;
for (int i = 0; i < n; ++i) {
sum += i;
}
return sum;
} Метод O(1):
int Method() {
var sum = 0;
for (int i = 0; i < 100_000; ++i) {
sum += i;
}
return sum;
} Как видно из примера, любой вызов первого метода с n < 100_000 будет отрабатывать быстрее, чем второй метод с константным временем выполнения. Так что когда вам говорят, что какая-то коллекция работает за константное время на добавление элементов, например, то это совсем не означает что она делает это максимально эффективно.