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

47 Views Asked by At

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$ ?

1

There are 1 best solutions below

0
On BEST ANSWER

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.