Practice question · Multiple choice
Appending to a dynamic array is described as O(1) amortised, even though some appends copy the entire array. What does the qualifier buy?
Hints
- Count the total elements copied across n appends when capacity doubles each time.
- 1 + 2 + 4 + … + n sums to what, roughly?
Show the answer
B. It averages the rare expensive copies over the many cheap appends
Why
Doubling means the copies form a geometric series summing to under 2n, so n appends cost O(n) in total and O(1) each on average. Amortised is a real guarantee about the total and not a worst case, which matters in real-time code, where one occasional O(n) pause can still miss a deadline.
Practise Arrays and Lists
The app has 5 more questions on this lesson, and keeps your place in the course. Mathematics I is free to start.
More questions on Arrays and Lists
- Arrays are indexed from 0, so a list of length 5 has valid indices 0 to 4 and a[5] is an error. Why has this…
- A list has length 5 and uses zero-based indexing. Sort each access.
- Let a be the list 3, 1, 4, 1, 5 with zero-based indexing. Select every TRUE statement.
- Match each array operation to what it does.
- A list b holds seven values. A loop runs i from 0 to 7 inclusive and reads b[i] each time. How many of those…