3 Arrays and Dynamic Arrays Free Online FlashCards

What is an array?

An array is a collection of elements stored in a fixed-size, ordered sequence.

What indices are valid in an array of length $n$?

For an array of length $n$, valid indices are $0, 1, 2, \ldots, n-1$.

How is an array element's address calculated?

Why is indexed array access $O(1)$?

Accessing or replacing an element by index takes $O(1)$ time because its address is calculated directly.

What are traversal's time and auxiliary-space costs?

Traversal visits every element, so it takes $O(n)$ time and $O(1)$ auxiliary space when no proportional extra structure is created.

What are linear search's best- and worst-case times?

Linear search takes $O(1)$ time in the best case and $O(n)$ time in the worst case.

Why is middle insertion in an array $O(n)$?

Insertion at the beginning or middle is $O(n)$ because elements must be shifted right to preserve order.

How does deletion position affect array complexity?

Deleting the last element is $O(1)$, while deleting from the beginning or middle is usually $O(n)$ because later elements shift left.

How can unordered deletion from an array be made $O(1)$?

If order is unnecessary, replace the deleted element with the last element and reduce the length; this makes deletion $O(1)$.

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 backing array can hold.

What happens when a dynamic array is full during append?

When full, a dynamic array allocates a larger backing array and copies or moves the existing elements, so that append costs $O(n)$ for that operation.

Why does geometric growth give amortized $O(1)$ append?

Geometric growth, such as doubling capacity, makes repeated appends $O(1)$ amortized even though an individual resize costs $O(n)$.