IntermediateMath for DSAUsed everywhere
1 + 2 + 4 + … + n < 2n
Doubling sizes add up to less than twice the last one. That's why dynamic arrays are O(1) per append and a full tree has 2ʰ⁺¹ − 1 nodes.
The idea
Each power of two is one more than the sum of all the smaller ones: 1 + 2 + 4 = 7 = 8 − 1. So 1 + 2 + … + 2ᵏ = 2ᵏ⁺¹ − 1, less than twice the last term.
A dynamic array (Python list, ArrayList) doubles when full and copies everything. Copies cost 1 + 2 + 4 + … + n < 2n in total, so n appends cost O(n): O(1) each on average. A perfect binary tree of height h has 1 + 2 + … + 2ʰ = 2ʰ⁺¹ − 1 nodes, half of them leaves.
Worked example
Appending 16 items to a list that starts with room for 1
- Resizes copy 1, 2, 4 and 8 items: 15 copies.
- Plus 16 writes. 31 operations for 16 appends: under 2 per append.
In code (Python)
def resize_copies(n):
capacity, copies = 1, 0
for size in range(1, n + 1):
if size > capacity:
copies += capacity # copy everything into a twice-as-big array
capacity *= 2
return copies
# resize_copies(16) == 15; always under 2nTotal work for n doubling steps is O(n).
How to spot it
- Anything that doubles: dynamic arrays, tree levels, repeated squaring, merge sort's levels.
Common mistakes
- Calling append O(n) because a single resize is O(n): the average is O(1).
- Forgetting a complete tree's last level holds about half its nodes.
Where it comes up
Go further
Up next for you · Beginner
“Have I seen this?” is a set →