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.

Maybe you need to factor in the GC algorithm when determining big O, since an algorithm which implements some complexity but creates a lot of garbage actually ends up with a worse big O?

Seems like a bit of a stretch to me but possible?