7 ms·

how gc influence time complexity? elaborate, pks

• slopinthebag 19d ago
  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?
  • chubot 19d ago
    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)
    • chubot 19d ago
      [dead]
    • emil-lp 19d ago
      You are assuming GC runs in linear time.
• emil-lp 19d ago
  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.