How to calculate $O(\sum_{k=1}^{K}(N-k)(k+1)^2)$?

Question

Using the formula for the sum of the squares and the sum of first $K$ numbers I can get that: $$\sum_{k=1}^{K}(N-k)(k+1)^2=\dfrac{1}{12}K(-3K^2+2K^2(2N-7)+3K(6N-7)+26N-10)$$

Now I guess I can simplify the formula if I would like to get the big-O. I think for $N=K$, it is fine for me. $$O(K^4).$$

What about $N>K$ and $N<K$ ?

It doesn't make much sense to consider $K > N$ here... – Yuval Filmus Mar 20 '16 at 22:30 — Yuval Filmus, Mar 20 '16 at 22:30
This looks like a math question, and belongs to math.se. – Yuval Filmus Mar 20 '16 at 22:30 — Yuval Filmus, Mar 20 '16 at 22:30

Sarvottamananda · Accepted Answer · 2016-03-21T14:54:31.743

If you are only interested in asymptotics then the sum is $O(\Sigma_{k=1}^K(Nk^2-k^3))$ which is equal to $O(NK^3-K^4)$.

If you have $K>N$ then the sum is negative. We can use Big-$O$ notation even for negative functions. Please refer https://en.wikipedia.org/wiki/Big_O_notation. So, in the case $K>N$ too, we can say that the sum is $O(NK^3-K^4)$ or $O(K^4-NK^3)$, as we take the absolute values of the function instead.

How to calculate $O(\sum_{k=1}^{K}(N-k)(k+1)^2)$?

1 Answers1