Задача на циклическую перестановку символов

[eoln]

Да.
Тут N и n разные числа.
n div 2 - количество итераций
N - зависимость, в данном случае линейная

[s-andriano]

Сообщение от Poma][a

А до какой константы? До N?

До произвольной.
По определению асимптотической оценки должна существовать такая константа С, что точно вычисленное количество операций для любых N больших некоторой нижней границы всегда меньше, чем С*N. (для оценки О(N). Соответственно, меньше С*N^2 для оценки O(N^2) и т.п.)

А если будет такой алгоритм :

for i := 1 to n div 2 do
    r := r + i;

То сложность будет тоже O(N)?

Конечно.

Асимптотическая оценка нужна для прогноза поведения времени выполнения при больших N.
Например, мы знаем, что для N = 1 000 000 время выполнения 10 с.
А нам нужно спрогнозировать, сколько времени потребуется для N = 10 000 000.
Так вот, для алгоритмов разной сложности оценка времени будет различаться:
O(1) : 10 c,
O(log(N)) : 10 c,
O(sqrt(N)) : 30 c,
O(N) : 100 c,
O(N*log(N)) : 100 c,
O(N*sqrt(N)) : 300 c,
O(N^2) : 1000 c,
...

[s-andriano]

Сообщение от eoln

Да.
Тут N и n разные числа.
n div 2 - количество итераций
N - зависимость, в данном случае линейная

Я бы сказал: N и O(N) - разные сущности, которые нельзя непосредственно друг с другом сравнивать.