How can I calculate the computational complexity of an equation composed of $2n$ multiplications and $2nm^2$ additions?

Question

I want to calculate the computational complexity in term of the big ($\cal O$). My equation is:

It composed of 2n multiplications and $2nm^2$ additions. The complexity of this equation is it ${\cal O}(2n + 2nm^2)$ or ${\cal O}(2n \cdot 2nm^2)$?

Answer 1

If the computation were done as it is written, there are $2N$ multiplications and $2N$ additions/subtractions inside the absolute value, but that is performed once for each $(r,s)$ pair, and there are approximately $M^2/2$ of those pairs, so $O(M^2 N)$. However, it's more efficient to first calculate and remember the $M$ numbers $\sum_j a_{rj} W_j$, rather than recalculating them each time. That would make the complexity $O(M^2 + N)$.

Answer 2

Consider how we use Big-Oh notation...

It may help to try to fit one term inside the other. For example, $O(n)$ means that the algorithm runs in time $c (n)$ for some $c$. $O(nm^2)$ means that the algorithm runs in time $c (nm^2)$ for some $c$.

You claim the running time is in $2n + 2nm^2$. So can you fit the number $2n + 2nm^2 < c(n)$ for some $c$. I suggest you try to fit $2n + 2nm^2 < c (nm^2)$. If you make $c =3$, Then $2n + 2nm^2 < 3(nm^2)$. So we know it is $O(nm^2)$.

---

But this is only part of the story. This just means that the algorithm will take more time than $c(nm^2)$ for some $c$. Robert Israel suggests using a different method. The idea is to store the two innermost sums in memory. Then the outermost sums take time $c(m^2)$ times the time to calculate the innermost sums. But you stored the innermost sums in memory, so they each only require $1$ unit of time to copy. So the time $c(m^2)$ times the time to calculate the innermost sums is really $c(m^2) 1$.

Now, the analysis is a little tricky. Remember that we first went through the innermost loops? There were $n$ values, so this clearly takes time $O(n)$. And you should get that the outer loops take time $c(m^2)1 = O(m^2)$. So what is $O(n) + O(m^2)$? Well, this is like comparing apples and oranges, because we don't know which is bigger. So in this case, we just add the two together, to get $O(n + m^2)$, which is the same as $O(m^2 + n)$. We can't simplify this sum any further, without more information.

---

If you knew that $m^2 > n$, then the algorithm could finish in time $O(m^2)$. If you knew that $n > m^2$, then the algorithm could finish in time $O(n)$. I hope you have an idea of why this is.