Challenge 1
- Algorithms course
- Expert
- Lesson 37/41
- 4 min
Print the amortized cost.
Challenge 1 - Amortized
The first challenge tests amortized analysis. The amortized cost of dynamic array append is O(1); we show this by counting doublings.
During n appends the array capacity doubles as 1, 2, 4, 8, ... The total number of doublings is floor(log2(n)).
You will now write a function that computes this count.
Practice count_doublings function
Write count_doublings(n). Return how many times the capacity doubles during n appends. Print 3 with print(count_doublings(8)).
Starter code
def count_doublings(n):
# Number of doublings during n appendsSample solution
def count_doublings(n):
# Number of doublings during n appends
count = 0
size = 1
last = 0
for i in range(n):
if last == size:
size *= 2
count += 1
last += 1
return count
print(count_doublings(8))Expected output
3
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Amortized cost of dynamic array append?
- O(1) Correct answer
- O(log n)
- O(n)
- O(n²)
Explanation: The amortized cost of dynamic array append is O(1).
2 doubling
Question
if last == size:
size *= ____
count += 1
Answer
if last == size:
size *= 2
count += 1Explanation: The capacity is multiplied by two.
3 Amortized concepts
| Term | Meaning |
|---|---|
amortized |
Average cost |
doubling |
Capacity growth |
O(1) |
Per append |
floor(log2(n)) |
Doubling count |