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?

Either one can happen depending on whether the array can be expanded (e.g.: there is more free space available in the same contiguous memory), see: http://en.cppreference.com/w/c/memory/realloc — UnholySheep, May 23 '18 at 13:11
duplicates from https://stackoverflow.com/questions/362760/how-do-realloc-and-memcpy-work — Robin Camus, May 23 '18 at 13:12
@nicomp I disagree. OP stated some information; that's not reasoning, that's recitation. Reasoning means analyzing the impact(s) of the information stated, considering various scenarios that would affect the answer, and so on. One you've considered the various scenarios it's basically self-answering, although the *exact* answer depends on the memory allocation library/mechanism in use. — Dave Newton, May 23 '18 at 13:38
@nicomp I'd add also that (to me) reasoning would also mean sharing the results of your own investigation, and that investigation would be required to show due diligence in the question. I mean, if you're smart enough to ask the question, you're certainly smart enough to do a fair amount of research, and likely reach the correct conclusion ("it depends"). But to request verification of an assumption on SO, IMO, sets the bar fairly high to show that due diligence YMMV. — Dave Newton, May 23 '18 at 13:50
@nicomp I'm not trying to be combative or divisive--I just think the question is reasonable self-answerable with suitable application of neurons is all. — Dave Newton, May 23 '18 at 14:13

Basile Starynkevitch · Answer 1 · 2018-05-23T14:09:30.880

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

Yes, I forgot to add the size of the type in order to avoid bugs and undefined behavior. But in this particular case that i explained at the topic, if i take the same array and resize it to one more cell, how many actions does the realloc function? — Asm ., May 23 '18 at 13:14
That's what i said. I do not take another pointer and relocate the memory for the array a through the new pointer. I take a pointer that keeps the array a address and do realloc on the same pointer like this => a = (int*) realloc (a, 11*sizeof(int)); — Asm ., May 23 '18 at 13:28
It's considered best practice in C [not to cast the result of `malloc` or `realloc`](https://stackoverflow.com/a/605858/169346) — JeremyP, May 23 '18 at 14:08

score 1 · Answer 2 · answered May 23 '18 at 14:09

1

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

answered May 23 '18 at 14:09

Art

19,807
1
34
60

Not exactly. Perhaps some `if (old_size == new_size) return old;` might happen (but that is not specified). So it is not exactly *equivalent*. BTW `internal_function_that_knows_old_size` might not be constant-time! – Basile Starynkevitch May 23 '18 at 14:10
1

@BasileStarynkevitch Which part of "It is possible for realloc to have optimizations that in some situations makes it faster" is unclear? And how is your comment relevant to the general case? Every specific case is O(1) which is why talking about big-O of specific cases is irrelevant. – Art May 23 '18 at 14:15
You claim `realloc` *is equivalent to* your code, and there is no equivalence but a supposition. My `realloc` in my answer is a possible (but silly) implementation, and there are many variants (e.g. doing some bit computation on addresses etc...) – Basile Starynkevitch May 23 '18 at 14:17
I would have upvoted your answer if you wrote: "realloc is often implemented with a code similar to", but since you claim that "realloc is *equivalent*", I downvoted your answer. For example, some *reasonable* implementations of `realloc` might start with `if (new_size > SOME_LARGE_LIMIT) return NULL;`; BTW, `realloc` in practice don't call `malloc` (but both call some *internal function*) – Basile Starynkevitch May 23 '18 at 14:20

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

2 Answers2