Время выполнения циклов for, где переменные зависят от внешних циклов

Question

У меня возникла небольшая проблема с пониманием времени выполнения вложенных циклов for. Я получаю это:

for(int x=0; x<10; x++) // runs 10 times
for(int y=0; y<n; y++) // runs n times

for(int i=0; i<n; i++)
    for(int j=0; j<n; j++) // runs n*n = n^2 times

Однако я запутываюсь, когда эти переменные связаны между собой. Например:

for(int i=0; i < N; i++) // runs n times
    for(int j=i+1; j<N; j++) // runs n*n times but 1 time less every pass?
        for(int k=j+1; k<N; k++) // ???

Можете ли вы указать мне правильное направление с простым объяснением того, как подойти к такой проблеме?

Answer 1

Вдохновленный ответом Скотта ...

В общем, формула - это мультипликативная формула для вычисления биномиальных коэффициентов (где n - это N сверху, а k - количество вложенных циклов (3)):

(n(n-1)(n-2)…(n-(k-1))) / k!

Продолжение чтения:

Биномиальный коэффициент

Падающая факторная мощность

И для специфический c анализ

Answer 2

Только для циклов i & j во втором примере счет будет (N-1) + (N-2) + ... + 3 + 2 + 1, который может быть показан быть равным N (N-1) /2.