title: What's the time complexity of realloc function in C?
body: <p>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 =></p>
  
  <pre><code>int *a = (int*)malloc(10*sizeof(int));
  </code></pre>
  
  <p>And then I want to resize this array to 11 in order to insert an additional value to the array a, so I do =></p>
  
  <pre><code>a = (int*)realloc(a, 11*sizeof(int));
  </code></pre>
  
  <p>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?</p>