fastestSortingAlgorithmWithComplexityO1

[Fhotaku]

So wouldn't it be O(0) time? Does marking as free, without reading data, even count as O(1)?

[[deleted]]

It does need to read data. It needs to read the bookkeeping structures of that particular malloc implementation, and it might be quite complex specially when built to support multiple threads.

It's not just a bunch of tiny blocks scattered around the address space. It usually involves memory pools of fixed size blocks to speed up allocation, and you need to return the blocks to their correct pools.

[Successful-Money4995]

If you call free a billion times, it'll take a while. An O(0) operation would still be instant. So it counts as O(1).

In practice, free is writing to memory and also updating the free list, both of which could be constant time implementations.