# Calculate the number of iterations in unusual nested loop

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

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

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?

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)$$.
• 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? – user122011 Jun 3 '20 at 17:32