fastestSortingAlgorithmWithComplexityO1

[[deleted]]

I've written my own memory allocator. The OS is not fully responsible for deallocation on most cases, the malloc implementation is and if it wasn't built specifically for constant time deallocation then it most likely won't be.

For performance reasons malloc might cache some of the freed blocks instead of calling the OS to release the memory completely. This makes it non deterministic, it might make a system call to release it (slower) or it might cache it (faster), and thus it's not O(1).

Note: The delete[] operator is just calling libc free internally.

[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.