What is the time complexity of generating a matrix using zeros(n). Is it n^2.

What is the time complexity of generating a matrix using zeros(n). Is it n^2.

Answer 1

[the cyclist]

I don't know the theoretical answer to this.

Practically, though, you can run this code to see that the generation time grows very slowly.

Here's some code that will generate matrices of growing size (up to the default maximum size, when it will error out).

N = 0;
STEP = 50;
KILO = 1000;
MILLI = 0.001;

figure
while true
    N = N + STEP;
    tic
    x = zeros(N);
    t(N/STEP) = toc;
    clear x
    plot((STEP:STEP:N)/KILO,t/MILLI,'.-')
    title('Time to generate zeros(N,N)')
    xlabel('N/1000')
    ylabel('Time [milliseconds]')
    drawnow
end

You'll get a different curve every time you try this, but a typical one I got looks like this:

You can see the growth. It's not easy to discern the shape, but regardless of the shape, the time to generate the largest matrix MATLAB can store (46350x46350 on my machine) is still only about 0.3 milliseconds.

[Walter Roberson]

Note that MATLAB accelerator might notice that the array is not used before it is cleared and so might not bother to do the allocation. You need to time the allocation and then you need to fetch from the memory so that MATLAB can't null out the operation. You should probably check the time after fetching from it too in case it delays allocation until then. You would compare that time to what is required to fetch from a matrix that was fully initialized and not being trashed to determine if it is indeed taking extra time for the first allocation.

Benchmarks are tough to get right to be sure you are measuring the right thing in a JIT environment.

[the cyclist]

I did not show the code here, but I actually also did some tests where I included a line like

x(N) = 1;

in there as well. I think that forces the allocation, right? The timings were not noticeably different.

Answer 2

[Walter Roberson]

Not necessarily. Provided there is readily available memory, the first overhead is constant time. After that the question becomes how the memory gets zeroed. In some memory allocation systems, memory is zeroed when it is added to the pool of memory, but more common would be that the memory would be zeroed when it was allocated. But zeroing memory is often delegated to special purpose hardware instructions, some of which will work in parallel for sufficiently large chunks of memory or memory that meets certain address requirements. Zeroing memory at time of allocation is sometimes handled by the memory management hardware, the part that maps between physical addresses and virtual addresses. Sometimes the contents of an entire block of physical memory is zeroed in constant time by the simple method of turning off power to the chip; sometimes an entire block of physical memory is zeroed by a special strobe line that tells the block to ground itself so as to zero the contents. A relevant term from my large computer days was "demand zero memory", which is virtual memory that (with hardware assistance) is always initialized as zero when the memory is received from the operating system.

Thus, for the special case of initializing with 0,sometimes it is constant time, sometimes it is grows proportional to ceiling(n^2/Blocksize), sometimes it is pure n^2, sometimes it would be a mix...

The one thing that it would not be would be order(n).