Tételezzük fel, hogy a méretet a realloc()-nál mindig duplázzuk és 1-gyel indítjuk, valamint hogy a realloc()-nak minden egyes alkalommal másolnia kell. A végső méret, amire szükségünk lesz, legyen "K". "K" helyett tekintsük a 2-nek azt az egész kitevőjű hatványát, amely nem kisebb, mint "K". Ez legyen "n".
K <= n = 2^t; t nemnegatív egész
Ebben az esetben a realloc által másolt byte-ok száma:
2^0 + 2^1 + 2^2 + 2^3 + ... + 2^(t-1) = 2^t - 1 = n - 1
Vagyis a másolások összköltsége O(n). A tömb szekvenciális feltöltése szintén O(n), tehát valamilyen konstans szorzóval romlik a teljesítmény.
A másolásra a libc feltehetően valamilyen szétoptimalizált, CPU és méretspecifikus rutint vet be. A feltöltést ezzel szemben jó eséllyel stdio-ból végezzük; a decimális- ill. hexafüzér-számábrázolást lebegőpontosra kell konvertálnunk (akár saját kézzel hívjuk a megfelelő rutint, akár az stdio hívja a kedvünkért).
Ítélet: a realloc() költsége észrevehetetlen lesz.
A másolgatást egy bizonyos méret felett egyébként is nagyon valószínűtlennek tartom. Ha nincs helyben elég nagy lyuk a virtuális címtérben, akkor sem kell feltétlenül a meglévő tömböt (= a kezdeti szakaszt) átmásolni, elég lehet a mögöttes lapokat más virtuális címtől újra-mappelni.
http://www.kernel.org/doc/man-pages/online/pages/man2/mremap.2.html
mremap() uses the Linux page table scheme. mremap() changes the mapping between virtual addresses and memory pages. This can be used to implement a very efficient realloc(3).