My friend told me that deletion of all the elements from vector in big O notation is quadratic performance is worst case (big O notation).

The worst case requires to delete always the first object, and all other elements are shifted to the left by one. So each deletion is linear because it depends on number of elements that need to be shifted.
I created a formula that describes this situation:

$\sum_{i=1}^n n(n-i)$

n - is array size (number of elements)
k - is a number of elements to remove (it is equal to the array size in my case)

Can we simplify or solve this formula somehow or write it another way?

Thanks in advance.


With no comment on whether or not your summation accurately models the situation described:

$$\sum\limits_{i=1}^n n(n-i) = n^2\sum\limits_{i=1}^n 1 - n\sum\limits_{i=1}^n i = n^3 - n\frac{n(n-1)}{2} = \frac{n^2(n-1)}{2} = \mathcal{O}(n^3)$$

To discuss the model, on the first deletion we shift $n-1$ elements, on the second we shift $n-2$, $\dots$, on the $i$th we shift $n-i$, etc. So, the summation should only be $$\sum\limits_{i=1}^n n-i = n\sum\limits_{i=1}^n 1 - \sum_{i=1}^n i = n^2 - \frac{n(n-1)}{2} = \frac{n(n-1)}{2} = \mathcal{O}(n^2)$$

However, this is highly dependent on the implementation of the "vector" and what it means to delete every element from such a vector.

  • $\begingroup$ I suggested that all operation except shifting one element to the left is constant. Thanks, I think that is one I needed. $\endgroup$ – Oleg Nov 8 '18 at 19:07

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.