alt Hacker NewsMaybe 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?
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?
It seems like that's pretty easy to disprove -- GC time is proportional to allocation time.
(allocation happens in the mutator, GC happens in the collector -- there is a symmetry)
The constant factor could be 500 or 50,000, but it's still proportional.
And allocations are some subset of the operations of the algorithm itself.
So then GC can't increase the overall time by more than a constant factor. So the big-O is the same.
(You could have some nuance on how to match GC operations to mutator operations, but the overall point is still true)