# big o notation for reallocs and frees

Hi,

Say d is the maximum amount of memory that can be used. So, the big oh notation for the Cprogram that uses the realloc function is O(log_2 d). Say d is freed. The reallocs up to d are not done in one step but in several steps. For example, first the memory used is 4 and then doubled to 8 later to 16 and then 32 and so on.

If d is freed in one step and then, memory is allocated to it via realloc up to d again (several times), would the big oh notation still be O(log_2 d)? Thank you.
ozo

It would depend on the implementation.
zizi21

ozo,
could you please give me an example. I am trying to understand this...I thought, it was log_2 d as you would take the largest one ...any help in understanding this would be greatly appreciated..
If d is the max amount of memory available that is used for the heap (i.e., not for code or stack or global data variables), then due to general fragmentation, it is unlikely that you will be to actually realloc d bytes.

But if you had more than d bytes available, and if you find that you can realloc up to d bytes without an error, then according to your OP is, it will take (log_2(d) - 1) realloc calls.

If you free this d bytes, and start over starting with a malloc of 4 bytes, and realloc'ing up to d bytes, then it still takes (log_2(d) - 1) realloc calls.

But, some of the realloc calls may require a new block to be formed if the current region cannot be doubled because some of the memory requird is already being used. In that case, the n-bytes in the original allocated region is copied over. The complexity of that single copy is O(n).

Worst-case would be that every realloc requires a copy. Consider this sequence:

8 + 16 + 32 + ... + 2^d ~ O(2^d)

Thank you very much..I am studying it now...

Thank you very much for looking into this. In the worst case, it is O(2^d) because each copy may require O(2^d) but in the best case, it is O(log_2 d). Is this right then ?
After all that, I'm going with ozo, in that it depends.

How often, in the grand scheme of things, is memory being reallocated?

What I see here reminds me of the doubling in size of an Array (say to implement an ArrayList, ArrayQueue, etc.).  In many cases the doubling operation happens so rarely, that updating the array (or heap region) is considered to happen at the speed of the underlying structure.  This could be as short as constant time.

My point is depending on what is going on, the effeciency may not matter to the overall efficiency of the program (or it may).  So, what is going on?
The OP gave the scenario that there would be a doubling in size of an array starting at 4, and then going to d. In that specific scenario there are about log_2(d) calls to realloc. There are implementation dependent under-the-hood optimizations that can improve one realloc version over another (e.g., if a copy is required, then copying 4-8 bytes at a time instead of one byte at a time), but for a given implementation, given the author's scenario, there are always log_2(d) calls to realloc.

Now, if one of the implementations were to reserve double or quadruple the number of pages actually requested in the realloc, then a number of realloc calls would natually be processed much faster since the reservation has already been made in advance.
off topic: @ hmccurdy - sent you a note via your website - did you get it?
SOLUTION
TommySzalapski

membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Thanks Tommy ...    Should have terminated with d, not 2^d, since the last operation would require copying d bytes. Rewrite:

In worst-case, if every realloc required a copy, then the total number of bytes copied is:
8 + 16 + 32 + ... + d = 2^3 + 2^4 + 2^5 + ... + 2^log_2(d) ;     Note: d = 2^log_2(d)

And this sum is just 2*(d-4) ~ O(d)
http://www.wolframalpha.com/input/?i=2%5E3+%2B+2%5E4+%2B...+%2B+2%5Ek

I agree that O(2^d) was too high. O( d * log_2(d) ) is a better estimate.
SOLUTION

membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.

membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.