What's the time complexity of realloc function in C?

Question

I have a question: what's the time complexity of realloc function? For example, I have an array of integers: a[10]. Of course, the array has been dynamically allocated in this way =>

int *a = (int*)malloc(10*sizeof(int));

And then I want to resize this array to 11 in order to insert an additional value to the array a, so I do =>

a = (int*)realloc(a, 11*sizeof(int));

My question is: What's the time complexity of reallocation? Does realloc simply add an additional cell into the array and then it takes O(1) or it recopies the whole array a, add the additional 11th cell and return the new-sized array and in this case the time complexity of this action is O(n)? Which assumption is true?

Answer 1

First, your code (in the original form of your question) is wrong. It should at least be

a = realloc(a, 11*sizeof(int));

(otherwise you probably have undefined behavior, in the usual case when sizeof(int) is greater than one). BTW realloc should not be casted in C.

Then, your question

What's the time complexity of realloc function in C?

Has no sense, unless you speak of some particular realloc function whose implementation you do know.

Notice that realloc is allowed to fail. Here is an efficient but useless and constant-time implementation of it (see also this answer; it is a standard conforming realloc which follows the letter, but not the spirit, of the standard n1570):

void *realloc( void *ptr, size_t new_size ) { 
  errno = ENOMEM;
  return NULL;
}

At last, in practice, you could consider malloc and realloc as somehow expensive operations (typical runtime could be several microseconds, so thousands of time slower than an addition), and in many cases you don't want to realloc on every loop. So you'll rather use some geometrical growth for realloc (like here)

Does realloc simply add an additional cell into the array and then it takes O(1) or it recopies the whole array a, add the additional 11th cell and return the new-sized array and in this case the time complexity of this action is O(n)?

Both can happen. You could imagine that malloc keeps somewhere the allocated size (rounded up by the implementation...) and in good cases realloc returns the same pointer (so O(1)) and in less happy cases it need to copy the memory zone elsewhere. Without knowing your particular implementation (of malloc, realloc, free) you cannot know what is the most common case, or their probability distribution. BTW, it seems that a realloc implementation which always copy data (or fail) is conforming to the standard (but inefficient). If you need to know more, you should benchmark.

At last, many implementations of the C standard library are free software (e.g. GNU libc, musl-libc, ...) and you might study their source code of malloc, free, realloc (above operating system primitives -usually system calls- growing the virtual address space; on Linux, something like mmap(2))

Answer 2

realloc is equivalent to:

void *
realloc(void *old, size_t new_size)
{
    size_t old_size = internal_function_that_knows_old_size(old);
    void *new = malloc(new_size);
    if (new == NULL)
        return NULL;
    size_t sz = old_size;
    if (new_size < old_size)
        sz = new_size;
    memcpy(new, old, sz);
    free(old);
    return new;
}

It is possible for realloc to have optimizations that in some situations makes it faster, but I'm pretty sure that it's impossible to make those optimizations always work, so the fallback will always be a function that does something like the above, so you should consider this your worst case.

Now, when it comes to time complexity, there is nothing in the standard that requires malloc or free have any reasonable behavior so it is possible that they will dominate the runtime of this function (or internal_function_that_knows_old_size will), but since those bits of the system are usually quite well written that is unlikely. The dominant part (at least for large n, which is where complexity is interesting) will be the memcpy.

So with some reasonable assumptions realloc has to be O(n) (with n being the old or new size of the allocation whichever is smaller).