Question

How many cost units are spent in the entire process of performing 40 consecutive append operations on an empty array which starts out at capacity 4, assuming that the array will double in capacity each time a new item is added to an already full dynamic array? As N (i.e., the number of appends) grows large, under this strategy for resizing, what is the average big-O complexity for an append?

How many cost units are spent in the entire process of performing 40 consecutive append operations on an empty array which starts out at capacity 4, assuming that the array will grow by a constant 2 spaces each time a new item is added to an already full dynamic array? As N (i.e., the number of appends) grows large, under this strategy for resizing, what is the average complexity for an append?

Answer 1

Question 1 :

- 40 consecutive push operations
- array of initial capacity 4
- double in capacity every time item added to full dynamic array
- what is big-o complexity?

Push Operations	Cost	Description
1	1
2	1
3	1
4	1
5	5	Copying Old 4 elements to new array, and appending new element , so total cost = 5 and New Size = 8
6	1
7	1
8	1
9	9	New Size = 16
10	1
11	1
12	1
13	1
14	1
15	1
16	1
17	17	New Size = 32
18	1
19	1
20	1
21	1
22	1
23	1
24	1
25	1
26	1
27	1
28	1
29	1
30	1
31	1
32	1
33	33	New Size = 64
34	1
35	1
36	1
37	1
38	1
39	1
40	1
Total Cost	100

Average Time Complexity for append operation : O(1)

Worst case Time Complexity for append Operation : O(n) where n = number of elements in the array

Question 2 :

- 40 consecutive push operations
- array of initial capacity 4
- grows by 2 elements in size every time item added to full dynamic array
- what is big-o complexity?

Push Operations	Cost	Description
1	1
2	1
3	1
4	1
5	5	Total Cost = 5 ( 4 + 1 -> Copy 4 elements and append 1 element ) New Size = 6
6	1
7	7	New Size = 8
8	1
9	9	New Size = 10
10	1
11	11
12	1
13	13
14	1
15	15
16	1
17	17
18	1
19	19
20	1
21	21
22	1
23	23
24	1
25	25
26	1
27	27
28	1
29	29
30	1
31	31
32	1
33	33
34	1
35	35
36	1
37	37
38	1
39	39
40	1
Total Cost	418

For all most half of the elements (n/2 ) elements, New array is being created and all the existing elements are being copied.

Average case time of append operation : O ( n/2) which is equivalent to O(n)  asymptotic time.