Prove that, in the process of growing an array incrementally from size 0 to size $n$, approximately n^2 values must be copied.

Question

Suppose that a precisely sized array is used to hold data, and that each time the array size is to be increased, it is increased by exactly one and the data are copied over.

Prove that, in the process of growing an array incrementally from size $0$ to size $n$, approximately $n^2$ values must be copied.

so here what I have tried. p.s I have no idea what I am doing here. I get that in order to loop though array of numbers than the timing is $n$.

[1] = 1 value
 |
[1, 2] = 2 values
 |  |
[1, 2, 3] = 3 values
 |  |  |
[1, 2, 3, 4] = 4 values
 |  |  |  |
[1, 2, 3, 4, 5, ..., $n$] = $n$ values

Answer 1

Okay so for n=2, you have n-1 (1) copies.

For n=3 you've got an ADDITIONAL n-1 copies (2)

For n=3 you've got an ADDITIONAL n-1 copies (3) ......

You just have to sum your |s

As you should know:

$$\sum_{i=1}^ni=\frac{1}{2}n(n+1)=\frac{1}{2}n^2+\frac{1}{2}n$$

That's where your squared comes from in the complexity.

See it now?

Answer 2

The first array has 1 value, the next has 2, the next has 3, and so on. We want to sum these, giving $$\sum_{k=1}^{n}k = \frac{n(n+1)}{2} = \frac{n^2 + n}{2} = O(n^2) $$

Note that the above is true because of the following: $$1+2+3+4+5+6+...+n$$ $$= n+(n-1)+(n-2)+...+1$$ If we add the corresponding terms of each series we get $(n+1)+(n+1)+(n+1)+...(n+1)$ This series has $n$ terms as well, yielding $(n+1)n$. We know that is the series added to itself, or the series multiplied by two. Thus, we have to divide by two, yielding $\frac{n(n+1)}{2}$

It would be very difficult for me to explain $O$ notation, so I recommend looking that up.