title: Is realloc in C linear?
body: <p>A Java <code>ArrayList</code> is O(n) if you're adding to the beginning, because <code>System.arraycopy()</code> is linear.<br />
  When making an ArrayList in C, i'd use <code>realloc</code> to reallocate the array when it gets full. Is <code>realloc</code> linear?</p>
  <p><code>ArrayList</code> in java is basically just a dynamic array. <code>System.arraycopy</code> is linear. That's what I know exactly. I think that it copies the input array into the output array element by element.</p>
  <p>Linear time complexity: The time it takes to complete a task is proportional to the amount of inputs. So copying an array element by element is linear, because it takes longer to finish the bigger the array.</p>