I was just wondering what the time complexity of free() is in C.
For example let's assume all my function does is:
for (int i = 0; i < n; i++) { free(ptr[i]); // this is just an example to show n pointers } Is it O(n) or O(n^2)?
1 Answer
As Story Teller has stated, the implementation of free() is not specified, which makes its time complexity unspecified, too.
The varied concepts of administrating allocated memory can come with different complexities.
Just a few simplified examples of data structures used by memory managers
(note that this is NOT the data structure in the program you created):
- a linked list of allocated blocks would come with a linear O(n) for a single malloc()-free() pair,
making your code O(n^2) - a buddy scheme would come with a logarithmic O(log n),
making your code O(n log n) - implementations stressing the time complexity of malloc and free (as an aspect of being fast), would probable come close to O(1), I am imagining hash-tables
(this would probably come with a penalty in memory consumption and with a "high 1", i.e. the constant time might be longer than for the other concepts with low n),
this would make your code O(n) (or O(1) for low n)
Note:
There is a scheme to make the memory manager data structures (applying to all examples above) within the administrated memory, that would allow finding the block to free and relative to it the administration data in O(1), resulting in a free() of O(1). The mentioned data structures, will however be searched by malloc() taking the mentioned different time complexities for an unused block (i.e. one which the size parameter to malloc() does not helpfully point to directly). Assuming that your code also has to malloc() the blocks you are freeing, you will probably actually end up with the mentioned complexities for the whole program.
Strictly speaking, with respect to only the shown freeing loop, any widely used memory manager will make your code O(n), with O(1) for each free().
(Thanks to Stargateur for forcing me to think more specifically about the exact situation this question is about.)
9 Comments
Billi
I am working with a linked list, and in each iteration one node is free'd. is it still O(n^2)?
Tony Tannous
@Billi, no, freeing one node at a time is
O(#nodes)
Stargateur
"a linked list of allocated blocks would come with a linear O(n) for a single free(), making your code O(n^2)" ??? linked list remove and insert operation are generally O(1) !
Stargateur
@Yunnosch I think you don't know what you are talking about, if malloc is implemented with a linked list, the next and prev pointer will be stock in the metadata of the pointer by malloc. You don't need to find the node through all the list. because the node will be something like
(struct header *)ptr - 1
Yunnosch
@Stargateur Yes you are right with that, too. I refer to that concept in my edited answer.
|
ptrevery time your example program just has undefined behavior.free()with respect to your externalnwill always be O(1). The function that contains this loop will be at least O(n).