enlarge:

   1. make new array of new size
   2. for each item in old array
          copy it to new array
   3. delete/recycle old array
   4. update info in vector struct

First scheme

   every time a new item is needed at the end
   of the array, enlarge the array to size+1,
   so there is no waste, array is always exactly 
   the right size.

adding ten things to an empty vector.

1. add A
   make new, 0 copy, 1 store, delete update

2. add B
   make new, 1 copy, 1 store, delete update

3. add C
   make new, 2 copy, 1 store, delete update

4. add D
   make new, 3 copy, 1 store, delete update

5. add E
   make new, 4 copy, 1 store, delete update

6. add F
   make new, 5 copy, 1 store, delete update

7. add G
   make new, 6 copy, 1 store, delete update

8. add H
   make new, 7 copy, 1 store, delete update

9. add I
   make new, 8 copy, 1 store, delete update

10. add J
   make new, 9 copy, 1 store, delete update

Total work to add ten things:

   10 make new array
   1+2+3+4+5+6+7+8+9 copy item
   10 copy new to end of array
   10 delete and update

10 x (make new, delete, update)
1+2+3+4+...+9+10 x (move data item fro one place to another)

total time = 10 x unknown-a + 55 x unknown-b

to add N things

total time = N x unknown-a + 0.5N^2 x unknown-b

Only care about the time when time is big enough
to notice, i.e. when N is big

so only useful fact is

   time approx. = some unknown x N^2

suppose under test, N=1000 items, it takes 1mS
(0.001 sec). 1,000,000 items needs 1,000 secs
approx quarter hour.

N small corporate database 100,000,000 items
would take 10^10 mS 10^7 seconds approx 4 months.

-----------------------------------

second scheme

   every time array needs to grow, increase it
   to size+3

1. new+delete + 1+0 copy
2.              1+0 copy
3.              1+0 copy
4. new+delete + 1+3 copy
5.              1+0 copy
6.              1+0 copy
7. new+delete + 1+6 copy
8.              1+0 copy
9.              1+0 copy
10.new+delete + 1+9 copy

copies to get up to N is
N + 3+6+9+12+15+21+24+...+N

etc. leads to 1/6 N^2 instead of 1/2 N^2

still same terrible fast growth.

------------------------------------

third scheme

   every time array needs to grow, increase
   to size*2.

1. 1+0 copy    size=1
2. 1+1 copy    size=2
3. 1+2 copy    size=4
4. 1+0 copy
5. 1+4 copy    size=8
6. 1+0
7. 1+0
8. 1+0
9. 1+8         size=16
....
17. 1+16       size=32
....
33. 1+32       size=64

for a large N
N copies for the new additions +
copies for enlargement 1+2+4+8+16+32+64+...+N

this is N + (the sum of the powers of 2 that are less than N)

Note that 1+2+4+8+16+32 = 63, one less than the next power of 2
1+2+4+8 = 15, one less than the next power of 2
1+2+4+8+16+32+64+128+256+512 = 1023, one less than the next

so the sum of 2^x that are less than N must be less than
the next power of 2, which is the first power of 2 that is
greater than N, which must be less than 2*N

total time to add N items to a vector by this scheme must
be less than 3*N copies