0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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)$.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$ – user122011 Jun 3 '20 at 17:32
  • $\begingroup$ @user122011 You're right. However, it does not change the asymptotic analysis. $\endgroup$ – OmG Jun 3 '20 at 17:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.