How to treat dynamic memory allocation in algorithm analysis? I have an algorithm in which I want to dynamically allocate some memory.
Let's say that I have N numbers and that I want to describe some binary relation over them. To do so I want to create a N*N matrix. But how fast is the memory allocation itself regarding N?

I do not want to zero out the new memory. In fact I do not want to touch it at all in this moment - I just want to allocate it and be sure that all of it is there.

I understand that the answer is: how is the memory allocation implemented?
Bit I hope that you can give me some upper bounds that are common for most of the popular memory management strategies.
You want to read


Wilson et al., Dynamic Storage Allocation: A Survey and Critical Review, 1995


and references therein, especially those to papers by Robson. Here is a quote that answers your question:


  Robson put [in 1974] a fairly tight upper and lower bounds on the
  worst-case performance of the best possible allocation algorithm. He
  showed that a worst-case-optimal strategy's worst-case memory usage
  was somewhere between $0.5M\log_2 n$ and about $0.84 M\log_2 n$.


Here, $M$ is the live memory, and $n$ is the ratio of the largest to the smallest block.

(So, if your algorithm allocates blocks of wildly different sizes, then you may want to think more carefully about how memory allocation works. This doesn't seem to be the case for the example given in the question.)

PS: I was searching for a link to Robson's article and I found this related CSTheory question: Data structure for dynamic memory allocation