19. Why is appending to a doubling dynamic array amortised O(1) even though some appends cost O(n)?
- The total copying cost over n appends is less than about n, so the average per append is constant
- Resizes never happen
- Copying is free in modern hardware
- Amortised means best case
Show answer
Answer: The total copying cost over n appends is less than about n, so the average per append is constant
Geometric growth makes the sum of all copies linear in n.
Lesson: Amortised Analysis
21. Why is the O(n · W) knapsack algorithm called pseudo-polynomial?
- It runs in O(n) time
- It only approximates the answer
- Its running time is polynomial in the value W, but exponential in the number of bits used to represent W
- It requires quantum computers
Show answer
Answer: Its running time is polynomial in the value W, but exponential in the number of bits used to represent W
Input size counts the digits of W, and W can be exponentially large in that digit count.
Lesson: P, NP and Intractable Problems