Say that you add and remove elements. Perhaps your data structure runs amortized constant time.

However, if the GC is, say, quadratic time, then this breaks the linearity of your algorithm.

This was indeed something that happened in recent releases og Python.