Big-O сложность вложенных для циклов

Question

Меня смущает сложность следующего (операция, выполняемая внутри внутреннего цикла, выполняется в постоянном времени):

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++)

Answer 1

Определенно O(n squared), конечно.Краткое объяснение для обоих случаев: 1 + 2 + ... + n равно n(n+1)/2, то есть (n squared plus n) / 2 (а в big-O мы отбрасываем вторую, меньшую часть, поэтому у нас остается n в квадрате / 2что, конечно, O(n squared)).

Answer 2

Вы правы, эти вложенные циклы все еще O (n ^ 2).Фактическое число операций близко к (n ^ 2) / 2, которое после отбрасывания постоянного коэффициента 1/2 равно O (n ^ 2).