6 ms·

They forgot to include GC overhead.

• feelamee 18d ago
  how gc influence time complexity? elaborate, pks
  • slopinthebag 18d 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 18d 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 18d ago
        [dead]
      • emil-lp 18d ago
        You are assuming GC runs in linear time.
  • emil-lp 18d 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.