У Кормена в его книге "Алгоритмы" приводится анализ кода сортировки вставкой, в частности количество выполнений строки:
for j<-2 to length[A]
указывается как n, но ведь если идти от двух, то количество выполнений будет равно n-1?
В теории алгоритмов это означает не ровно n, а сопоставимо с n. То есть время будет зависеть от этого самого n. Как пример, часто используются алгоритмы с такими двумя вложенными циклами:
for(i = 0; i < n; i++)
for(j = i + 1; j < n; j++)
// ...
Количество итераций в данном случае будет
(n * (n - 1)) / 2
, но на практике такой алгоритм является квадратичным.
http://habrahabr.ru/post/104219/ вот неплохая статья для начинающих