big o notation for reallocs and frees
Posted on 2013-01-06
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.