SME
Data Structures & Algorithms · Problem type
Cost of a growing array
Use this for “An array starts with 1 slot and doubles when full. How many items are copied while 1000 are pushed?”
This is an example. Type your own values to start a new problem.
n
Items pushed
example
k
Doublings
calculated
m
Final capacity
calculated
T
Items copied
worked out (not typed)
a
Copies per push
worked out (not typed)
W
Total writes
worked out (not typed)
Formulas
k
=
⌈log₂
n
⌉
10 = ⌈log₂ 1,000⌉
m
=
2
k
1,024
=
2
10
T
=
m
−
1
1,023 = 1,024 − 1
a
=
T
n
1.023
=
1,023
1,000
W
=
n
+
T
2,023 = 1,000 + 1,023
Assumptions
•
The array starts with 1 slot; when a push finds it full, it moves to a new array twice the size.
•
Each doubling copies every item already held, so all the copies add to 1 + 2 + 4 + …, one less than the final capacity.
•
Every push also writes its own item once; that costs one step whether or not the array grows.
Step-by-step
WE KNOW
n = 1,000
FIND
doublings (k), final capacity (m), items copied (T), copies per push (a), total writes (W)
Step 1 · Find doublings (k)
Use k = ⌈log₂ n⌉
Each
doubling
multiplies
the
capacity
by
2,
so
take
the
fewest
doublings
that
make
2ᵏ
at
least
n
.
⌈log₂
1,000⌉
=
10,
since
2
9
=
512
<
1,000
≤
1,024
=
2
10
k
=
10
Step 2 · Find final capacity (m)
Use m = 2ᵏ
Starting
from
1
slot,
k
doublings
give
2ᵏ
slots.
m
=
2
10
m
=
1,024
Step 3 · Find items copied (T)
Use T = m − 1
The doublings copy 1 + 2 + 4 + … + 2ᵏ⁻¹ items, and that sum is 2ᵏ − 1.
T
=
1,024
−
1
T
=
1,023
Step 4 · Find copies per push (a)
Use a = T ÷ n
Spread the copies over every push: under 2 each, so a push costs constant time on average (amortized).
a
=
1,023
1,000
a
=
1.023
Step 5 · Find total writes (W)
Use W = n + T
Each push writes its own item once, and the doublings add the copies.
W
=
1,000
+
1,023
W
=
2,023
Check
Put the numbers back in. Both sides should match.
10 = ⌈log₂ 1,000⌉ ✓
1,024
=
2
10
✓
1,023 = 1,024 − 1 ✓
1.023
=
1,023
1,000
✓
2,023 = 1,000 + 1,023 ✓
Topic check
See what you know: 5 questions on this topic
New questions each time. Pass to mark it complete.
Related lessons
Lists, stacks and queues
Main lesson
Circular queue indices
Use this for “A circular queue has 8 slots, its front at slot 6 and 4 items. Where is the last item, and where does the next one go?”
Address of an array element
Use this for “A two-dimensional array of 8-byte numbers starts at address 2000 and has 10 columns. Where is element (3, 4)?”
Evaluate a postfix expression
Use this for “Evaluate the postfix expression 3 4 + 2 × 7 − with a stack.”