I need to compute the computational complexity in big-O notation of the following double nested loop,

Let S={1,2,...,N}, T={1,2,...,M} then we have summation of two variable J and K on these sets as

$$\sum_{m=1}^{M} \sum_{n=1}^{N} (J_{n,k}K_{n,k})_m \quad \forall k \in S$$

The variable k is defined for all values on set S

The issue here is that we do not sum on variable k which is troublesome to me.

Any help is appreciated!


  • $\begingroup$ It's a bit ambiguous, it could be that $k$ is just fixed and you do the calculation for a single value of $k$, or it could be that you need to do the calculation for each possible value of $k$ and add them up.(Also, I don't understand why the upper limits are $S$ and $T$, should they be $N$ and $M$?) Also, you haven't said what $*$ and subscript $m$ mean. $\endgroup$
    – Ian
    Nov 28, 2016 at 12:43
  • $\begingroup$ Thanks Ian for valued correction. I have updated the post in regard of your comments. Please note that we need to compute J times K for every possible k. $\endgroup$ Nov 28, 2016 at 13:22
  • $\begingroup$ OK. Now what's the subscript $m$ doing exactly? Why is $J_{n,k} K_{n,k}$ subscriptable, is it a vector or something? $\endgroup$
    – Ian
    Nov 28, 2016 at 16:19
  • $\begingroup$ No actually I want to compute $J_{n,k} K_{n,k}$ and sum for every $m\in T$. For example, Let N=2, M=2 then I want to compute followings: $ ({J_{1,1} K_{1,1}+J_{1,2} K_{1,2}})_{m=1}+({J_{1,1} K_{1,1}+J_{1,2} K_{1,2}})_{m=2}$ $\endgroup$ Nov 29, 2016 at 1:25
  • $\begingroup$ So $J$ and $K$ are functions of $n,k$ and $m$? I still don't know what the subscript means. Would an equivalent way to write the problem be $\sum_{m=1}^M \sum_{n=1}^N \sum_{k=1}^K J_{n,k}(m) L_{n,k}(m)$ (where my $L$ replaces your $K$, since I needed to use $K$ for something else)? $\endgroup$
    – Ian
    Nov 29, 2016 at 1:31


You must log in to answer this question.

Browse other questions tagged .