In the lecture of week2 there is the following slide:
.
The O(n-k) complexities are also amortised, without amortisation those are O(n)