Оценка вычислительной сложности элементарного алгоритма

[TokSeven]

На днях возник вопрос следующего содержания: имеем двойной цикл вида (всё на псевдокоде)

for (i = 0; i < n; ++i)
  for (j = 0; j < n; ++j)
  {
    //действия за константное время
  }

Данный алгоритм имеет сложность порядка Θ(n^2)=O(n^2).

Далее, имеем двойной цикл следующего вида

for (i = 0; i < n; ++i)
  for (j = i + 1; j < n; ++j)
  {
    //действия за константное время
  }

Вопрос: возможно ли точно определить вычислительную сложность Θ(...) данного алгоритма, и, если да, то чему она равна? Насколько мне известно, данный алгоритм также имеет O(n^2).

[Streletz]

Насколько мне известно, данный алгоритм также имеет O(n^2).

Вполне вероятно, что это действительно так. Хотя точное исследование ИМХО будет не лишним.

возможно ли точно определить вычислительную сложность Θ(...) данного алгоритма, и, если да, то чему она равна?

В помощь:Понятие вычислительной сложности алгоритма, О-нотация. Эмпирические оценки эффективности алгоритмов на примере алгоритмов сортировки.

[Poma][a]

Угу.. Оба будут квадратами.. но 1-ый - O(C1*N^2) 2-ой - O(C2*N^2)..
где С1 > С2.. но константы не пишутся.. посему мы понимаем, что сложность они имеют N^2.. но один будет выполняться быстрее другого..

[evg_m]

но 1-ый - O(C1*N^2) 2-ой - O(C2*N^2)..

O(n*F(n)) где F(n)<n
O(n*ln(n))

[ds.Dante]

Количество итераций в зависимости от n:
2: 1
3: 1+2
4: 1+2+3
5: 1+2+3+4
6: 1+2+3+4+5
...
N: N*(N-1)/2

O(N) = N^2

Ромаха прав.