What is the time cost (asymptotically) of the following method?:
void fillList(int i)
{
list = new int[i];
}
I have been told that it takes O(1) time because no initialization is done and the needed space is allocated as a whole, but others say that it takes O(n) time because the memory for each element is still reserved and "touched". Thus, it's not clear to me what the time cost is here.
I guess list = new MyUserDefinedClass[i] takes O(n) time if it has a constructor, so each element has to be constructed one after another. But can it be O(1) somehow? Maybe with default constructor?
And what about delete? Same time cost as new?
The official answer is that the standard just doesn't specify it.
In reality, it's unknowable. The first allocation of a program may be really fast, because the heap consists of only one big block of unallocated memory. A later allocation of exactly the same size in the same program (after allocating and freeing many blocks of memory) may walk through many free blocks to find one that can fulfill the allocation, so it may be many times slower.
If all the memory is in use, the OS may need to flush some dirty pages to disk before the memory can be allocated. This is generally about linear on the number of pages--but any size up to one page will take roughly the same length of time. But one more byte roughly doubles the time.
From there it gets even complex though: The page might be flushed to an SSD, or it might be flushed to a spinning disc. The drive unit might or might not have an onboard cache (most do, nowadays). But if it does, that might be anywhere from completely empty to completely full.
And of course, whether that's necessary will depend (heavily) on what programs are using how much memory. Most OSes will try to keep at least a few pages ready to be allocated at almost any time. But if (for example) something allocates and writes a lot of data quickly, that can affect not only that program, but everything else running on that system.
You can set a lower bound on the time for some cases, but it's almost impossible to even guess at the upper bound.