02 Arrays and Dynamic Arrays Free Online FlashCards

What is the valid index range of a zero-based array of length $n$?

The first element is at index $0$, and the last element of an array of length $n$ is at index $n-1$.

How is an array element’s address calculated?

$\operatorname{address}(A[i]) = B + i \times w$, where $B$ is the base address and $w$ is the element size in bytes.

What is the typical time complexity of indexed array access?

Accessing or updating an element by a known index is typically $O(1)$ because its address can be calculated directly.

How does an array index differ from an array value?

An index identifies a position; a value is the data stored at that position. For example, $29$ is the value at index $2$.

What is the time complexity of traversing an array?

Traversing an array of $n$ elements takes $O(n)$ time because each element is visited.

What happens to existing elements during array insertion?

Insertion at index $i$ shifts every existing element from index $i$ onward one position to the right.

Why does array insertion shift elements from right to left?

The loop moves elements from right to left so each value is copied before its destination can overwrite it.

How does array deletion close the removed element’s gap?

Deletion shifts later elements one position left to close the gap left by the removed element.

Why are middle insertions and deletions usually $O(n)$?

Insertion or deletion at the beginning or middle usually takes $O(n)$ time because elements must be shifted.

What is the difference between dynamic-array size and capacity?

Size is the number of elements currently stored; capacity is the number of elements the allocated storage can hold.

What happens when a dynamic array becomes full?

It allocates a larger backing array, copies the existing elements, replaces the old backing array, and inserts the new element.

What is the amortized complexity of appending to a dynamic array?

With geometric capacity growth, appending is $O(1)$ amortized, although an individual resize can take $O(n)$ time.