Calculate the number of iterations in unusual nested loop

Question

I am trying to calculate the number of iterations of a sequence of nested loops of the form:

\begin{equation} N = \sum_{j=0}^{j_T} \sum_{k=0}^{j} \sum_{l=0}^{k} \sum_{n=n_0}^{n_T} 1 \end{equation}

where $j_T\ge 0$ and $n_T\ge 0$ are known constants.

For $n_0 = 0$ the case is trivial and can be calculated using the standard procedure (Sum number of times statement is executed in triple nested loop)

The problem is that in my case $n_0$ is given by a more complex expression:

$$ n_0 = \begin{cases} 0 &\text{ if } k-2l\lt0,\\ n_T &\text{ if }k-2l\gt n_T,\\ k-2l &\text{ otherwise.} \end{cases} $$

Basically, the initial value of $n$ in the last sum is $k-2l$, except when its value is lower/greater than the lower/greater limits of the sum, in which case it gets replaced by the corresponding extreme value of the interval (either 0ドル$ or $n_T$).

Any ideas?

• D.W.: Please don't deface your question by removing all of its content.

Answer 1

If you want to compute an upper bound of the asymptotic complexity, you can consider the maximum value for the most inside sum. Hence,$\sum_{n=n_0}^{n_T}1 \leqslant n_T + 1$. Therefore, we will have:

$$ N \leqslant \sum_{j=0}^{j_T}\sum_{k=0}^j\sum_{l=0}^k (n_T+1) = \sum_{j=0}^{j_T}\sum_{k=0}^j (n_T+1) (k+1) = (n_T+1) \sum_{j=0}^{j_T}\sum_{k=0}^j (k+1) = $$ $$ (n_T+1)\sum_{j=0}^{j_T}\frac{(j+1)(j+2)}{2} = \Theta(n_T (j_T)^3) $$

Therefore, $N = O(n_T (j_T)^3)$.

• user122011: Shouldn't be $\sum_{n=n_0}^{n_T}1 \leqslant n_T+1,ドル since the lowest value of $n$ is $n_0=0$? This would lead to the standard form of the problem with all sums starting at zero, which would lead to $N=(n_T+1)(j_T+1)(j_T+2)(j_T+3)/6$. Am I missing something?
• OmG: @user122011 You're right. However, it does not change the asymptotic analysis.