3 Arrays and Dynamic Arrays

1. Structure and indexed access

An Array stores elements in an ordered sequence. Each element has a position called an index, and indexing normally begins at $0$. Therefore, an array with $n$ elements uses indices from $0$ through $n-1$.

For example, in the sequence $[18,7,25,4]$, the element at index $2$ is $25$. The index identifies the position; it does not indicate the element’s value.

Array elements are stored in Contiguous memory. If every element occupies the same number of bytes, the address of element $i$ can be computed directly:

Because the address calculation takes a constant number of steps, accessing or replacing an element by index takes $O(1)$ time. Contiguous storage also tends to provide good Cache locality, which supports efficient sequential processing and keeps memory overhead relatively low.

Takeaway: Direct indexing is fast because an array combines zero-based positions with a predictable, contiguous layout.

2. Traversal and searching

Traversal means visiting elements in sequence, often from the first position to the last. A complete Traversal of $n$ elements takes $O(n)$ time because every element is processed once. If no additional structure that grows with $n$ is created, the auxiliary space is $O(1)$.

A search can also use a traversal. Linear search checks one element at a time and returns the matching index when it finds the target. If the first element matches, the best-case time is $O(1)$. If the target is last or absent, the worst-case time is $O(n)$.

The same complexity applies to both fixed arrays and dynamic arrays because both require checking positions one at a time when the data is unsorted.

Takeaway: Visiting or searching every possible position is linear in the number of elements, even though accessing one known position is constant time.

3. Fixed-size updates

A fixed-size array receives its capacity when it is created. Its length cannot be increased directly. If the array is full and another element is needed, a larger array must be created and the existing elements copied into it.

Insertion must preserve the order of elements. To insert at index $i$, elements from the end down to index $i$ are shifted one position to the right. Inserting at the end takes $O(1)$ when unused space is available, but inserting at the beginning or middle can shift $O(n)$ elements and therefore takes $O(n)$ time.

Deletion works in the opposite direction. After deleting index $i$, later elements shift one position to the left. Deleting the last element takes $O(1)$ when order is maintained, while deleting from the beginning or middle takes $O(n)$.

If order does not matter, a deleted element can sometimes be replaced with the last element before reducing the logical length. This can make deletion $O(1)$, but it changes the order of the remaining elements.

Takeaway: Array updates are inexpensive at the end but expensive away from the end because order requires shifting elements.

4. Dynamic growth and amortized appending

A Dynamic array combines indexed access with automatically managed storage. It maintains both Size, the number of elements currently stored, and Capacity, the number of positions available in its backing array. For example, size $=3$ and capacity $=5$ means that three positions are occupied and two more are available without allocation.

When an element is appended and size is less than capacity, the element is placed in the next free position, so the operation takes $O(1)$ time. When the backing array is full, the structure allocates a larger array, copies or moves the existing elements, and then inserts the new element. That particular append takes $O(n)$ time.

Dynamic arrays usually grow geometrically. A common illustrative rule is:

The exact growth factor is an implementation detail. The important principle is that capacity should grow by meaningful multiples rather than by one position at a time. If capacity increased by only one position for every append, the total copying across $n$ appends would be proportional to $1+2+3+\cdots+(n-1)$, which is $O(n^2)$. With geometric growth, the total copying across a long sequence of appends is $O(n)$, giving an Amortized time complexity of $O(1)$ per append.

A dynamic array may also shrink when its size becomes much smaller than its capacity. Shrinking too aggressively can cause thrashing, in which repeated growth and shrink operations waste time. A threshold-based policy avoids shrinking after every small deletion.

Takeaway: An occasional expensive resize is acceptable because geometric growth spreads its cost across many appends.

5. Choosing the right array strategy

The main operation costs can be summarized as follows:

• Access by index: $O(1)$ for both fixed and dynamic arrays.

• Update by index: $O(1)$ for both structures.

• Traversal: $O(n)$.

• Linear search: $O(n)$ in the worst case.

• Append with available capacity: $O(1)$.

• Append that causes a resize: $O(n)$ for that individual operation.

• Append in a dynamic array, amortized: $O(1)$.

• Insert or delete at the beginning or middle: $O(n)$.

• Delete at the end: $O(1)$.

Dynamic arrays are a strong default when a program needs fast indexed access, efficient traversal, compact storage, and frequent appends near the end. They are less suitable when insertions or deletions near the beginning or middle occur frequently, because shifting elements remains linear.

If the final number of elements is known or can be estimated, reserving capacity in advance can reduce reallocations. Reservation should generally happen in meaningful batches; reserving one additional position before every append can undermine the benefit of geometric growth.

Final takeaway: Choose arrays or dynamic arrays when direct access, sequential processing, and end-based growth matter most. Consider another structure when frequent middle updates matter more than compact contiguous storage.