Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What is the time complexity of free()?

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)?

like image 914
Billi Avatar asked Oct 16 '25 10:10

Billi


1 Answers

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

like image 50
Yunnosch Avatar answered Oct 18 '25 23:10

Yunnosch