Big O analysis of garbage collection runtime cost

When reasoning about runtime cost in a garbage collected language, what is the cost of a statement such as myList = null; in terms of 'n' (the number of elements in the list)? For sake o开发者_如何转开发f argument, consider the list to be a singly linked list of reference types with no finalisation required.

More generally, I'm looking for any information on how runtime cost can be analysed in a language with GC.

My own thought is that the cost is likely to be either O(1) or O(n) depending on the collector implementation. In a mark and sweep collector the unreachable objects simply won't be reached, so I could imagine there being no cost associated with clearing them. (Infact there is an ongoing cost simply keeping objects alive, presumably amortised by using generations.) Conversely in a simple reference counting collector I could easily imagine it costing O(n) to do the cleanup...

It's not obvious to me how to reason about this when designing algorithms..

I suspect you can assume the amortized costs of that statement to be O(1). In practice, that is what I do, and I have never found situation that made me suspect this assumption to be incorrect.