Array

Definition

Sequentially stored data in a continuous chunk of memory. Two types:

• Linear: fixed size
• Dynamic: reserves space for additional elements, when full allocates new chunk with double size and copies the previous values.

Pros and Cons

Pros: Fast access to elements.

Cons: Slow insertion.

Complexity

Operation	Complexity - Linear	Complexity - Dynamic
Access	$O(1)$	$O(1)$
Search	$O(n)$	$O(n)$
Append	N/A	$O(n)$ but $O(1)$ amortized cost
Insertion	N/A	$O(n)$
Delete	$O(n)$	$O(n)$

• Access: access through start + (cellsize * index) (cellsize being different for each type).
• Search: iterates through array and checks if the current value is the searched one.
• Append: if full, copies every value in new memory chunk, however thanks to the additional space in most cases the new chunk is not required.
• Insertion: if full, copies every value in new memory chunk, then shifts array and adds element.
• Deletion: removes value and shifts array.

Proof for amortized cost

In the case we add m elements to dynamic array

cost of doubling (nb copies): $n_c = 1 + 2 + 4 + ... + m/2 + m$
total number of operations: $n_{tot} = n_c + m = 3m$

So appending m elements is $O(m)$, hence appending 1 element is $O(1)$ on average.