← DSA I

Contiguous memory laboratory

Array & Dynamic Array Lab

0/11 traced

Append (insert at end)

Compare a spare-capacity append against one that must grow the buffer first.

worst case O(n) time O(n) space
1#include <vector>
2// Fixed counterpart: std::array<int, N>.
3// std::vector supplies native storage; size/capacity stay explicit for tracing.
4struct DynArray {
5 std::vector<int> slots;
6 int size;
7 int capacity;
8};
9
10void append(DynArray& a, int v) {
11 if (a.size == a.capacity) {
12 int nextCapacity = a.capacity == 0 ? 1 : 2 * a.capacity; std::vector<int> bigger(nextCapacity);
13 for (int i = 0; i < a.size; ++i) {
14 bigger[i] = a.slots[i];
15 }
16 a.slots.swap(bigger); a.capacity = nextCapacity; // retired storage follows RAII
17 }
18 a.slots[a.size] = v;
19 a.size += 1;
20}
size5
capacity5
inull
readIndexnull
writeIndexnull
appendsCompleted0
totalElementCopies0

Modeled slot addresses: base 0x100 + index × 4-byte teaching slot. Native C/C++ uses sizeof(int); Java and Python expose indexed elements rather than stable raw addresses.

Buffer · size 5 / capacity 5

0 7 model 0x100
1 14 model 0x104
2 21 model 0x108
3 28 model 0x10C
4 35 model 0x110
In sizeSpare capacity ShiftedCopied Read / write this line
Exact work through this line 3 +3 on this line
O(n) time O(n) auxiliary space 0 peak reported values
1comparisons
2reads
0writes
0pointer reads
0pointer writes
0swaps
0allocations
0deallocations
0node visits
0iterations
0calls
0returns
Variables before line

size5

capacity5

oldCapacitynull

inull

readIndexnull

writeIndexnull

appendsCompleted0

totalElementCopies0

resultnull

resultIndexnull

slots[0]=7 · [1]=14 · [2]=21 · [3]=28 · [4]=35

Variables after line

size5

capacity5

oldCapacitynull

inull

readIndexnull

writeIndexnull

appendsCompleted0

totalElementCopies0

resultnull

resultIndexnull

slots[0]=7 · [1]=14 · [2]=21 · [3]=28 · [4]=35

Reads, writes, and state changes on this line

operation-count.value 0 → 3 highlight

Why this bound?

O(n) time · O(n) space

worst
slot 1slot 2slot 3slot 4slot 5 Work can grow once per affected slot → n
Auxiliary memory model
slot 0slot 1slot 2slot 3slot 4

A second/resized buffer can hold a linear number of slots, so peak auxiliary storage is O(n).

  1. size == capacity == 5, so a 10-slot buffer is allocated first.
  2. All 5 elements are copied — one read and one write each — before the new value lands.
  3. The copy loop grows linearly with n: O(n) time and O(n) transient auxiliary space.
Assumptions behind this claim
  • Logical elements occupy consecutive indexed backing slots; only the explicit C-style teaching model exposes base + index × slot size.
  • A full buffer grows by doubling its capacity before the write.
  • Installing a grown backing store counts the backing-reference and capacity writes; C frees its retired allocation explicitly, while C++ lifetime rules and Java/Python runtimes govern physical reclamation, which is outside the portable count.
  • size == capacity when the append starts.
  • Each displayed read, write, comparison, allocation, or copy is one counted primitive.
  • Trace construction and visualization bookkeeping are excluded from the algorithm count.
Step 1 of 16 · append-capacity-check Check capacity: size 5 vs capacity 5

size equals capacity — there is no free slot, so the buffer must grow first.

About this implementation

A dynamic array keeps elements contiguous. Access is O(1) index arithmetic; inserting or deleting anywhere but the end shifts every following element (O(n)). Appending is O(1) when a spare slot exists, but O(n) when the buffer is full and must double — averaged over many appends, doubling keeps it amortized O(1). Compare to C arrays (fixed), C++ vector, Java ArrayList, and Python list, which all grow this way underneath.

1 / 16