О временной сложности Insertion-sort

Question

Конспект лекции Вот мой конспект, и я просто не могу понять, почему, когда j = от 2 до n, время этой операции равно n?почему времена не н-2?Вот моя причина, если j = 2 & n = 3, в этом случае внешний цикл запускается только один раз.Если время равно n, как сказано в примечании к лекции, то время в приведенном выше примере равно 3, но на самом деле его выполнение выполняется только один раз.Пожалуйста, помогите.

Answer 1

Да, вы правы, но мы вычисляем асимптотическую сложность.

так как n становится очень большим, постоянные факторы начинают иметь значение все меньше по сравнению с факторами п. Разница между 2n и n ^ 2 для большое n намного более значимо, чем разница между 2n и 3n. Итак, чтобы упростить вещи, мы можем просто отбросить постоянные факторы и мы остались с O (n). источник