Читаю в книге Кормен: Алгоритмы построение и анализ анализ алгоритмов
При условии, что
for (int j = 2; j <= n; j++) будет n-1 повторов проверки условия цикла
При условии, что
for (int j = 2; j < n; j++) будет n-2 повторов проверки условия цикла
Откуда берется n повторов?
Блин, люди, вы о чем? Какая сложность? Здесь расписывается количество операций каждой инструкции. Сколько раз выполнится строчка for в данном случае:
n = 0
for i = 2 to n:
print i
Ни разу? А вы уверены? Ни разу не выполнится print, а условие хотя бы раз, но проверяться будет: первое выполнение сделает i равным 2 и проверит, что i больше n. Т.к. оно будет большим (т.к. 2 > 0), то остальное выполняться не будет. Вот и получается - for здесь выполнится один раз, а print ни разу.
UPD: про саму задачу забыл написать
for j = 2 to n
Первый проход - j = 2, j <= n, поэтому выполняем тело цикла
Второй проход - j = 3, j <= n, поэтому выполняем тело цикла
...
n-1 проход - j = n, j <= n, поэтому выполняем тело цикла
n проход - j = n + 1, j > n, поэтому тело цикла не выполняем
Вот и получается - тело цикла было выполнено n-1 раз, а сама инструкция for была выполнена n раз, причем последнее выполнение просто проверяет, что цикл больше выполнять не надо.