Меня смущает сложность следующего (операция, выполняемая внутри внутреннего цикла, выполняется в постоянное время):
for(int i=0; i<n; i++)
for(int j=i; j<n; j++)
это O(n^2) или O(n)? Я вычисляю O(n^2). Есть идеи?
также меня интересует следующее:
for(int i=0; i<n; i++)
for(j=0; j<i; j++)
Однозначно O(n squared), конечно. Краткое объяснение для обоих случаев: 1 + 2 + ... + n равно n(n+1)/2, то есть (n squared plus n) / 2 (и в большом-O мы опускаем вторую, меньшую часть, поэтому у нас остается n в квадрате / 2, что, конечно, равно O(n squared)).
Вы правы, эти вложенные циклы все еще O (n ^ 2). Фактическое количество операций близко к (n ^ 2)/2, что после отбрасывания постоянного коэффициента 1/2 равно O (n ^ 2).
