Why is this simple loop taking so much time?

Why is this simple loop taking me so much time?

n=2^13;

idx=cell(2*n-1,1);

for i=1:2*n-1
    temp=zeros(i,2);
    for j=1:i
        if j>n
            idx1=0;
        else
            idx1=j;
        end
        if i-j+1>n
            idx2=0;
        else
            
            idx2=i-j+1;
        end
        temp(j,:)=[idx1,idx2];
    end
    idx{i}=temp;
end

Answer 1

[Walter Roberson]

When i is a particular value, say M, then you do M loop iterations total over the j. If we were to say that each loop iteration took time "1", then M of them takes time M. When i was one fewer, M-1, then you did M-1 operations for that, and one fewer still, M-2, you did M-2 operations for that. The total number of operations by the time of doing i = M is 1+2+3+4...+M, which is M*(M+1)/2 .

So by the end of 2^13 operations, you are doing 2^13 * (2^13+1) / 2 = 2^12 * (2^13+1) = 33558528 operations.

... and that is going to take a while.

On my system, n = 2^10 took roughly 1/4 second, for what would have been 2^10*(2^10+1)/2 = 524800 operations. If each loop was constant time we could predict 33558528 / 524800 * 0.25 = about 15 seconds.

Elapsed time is 14.064167 seconds.

Close enough.

[Mohamad Al Hassan]

Is there any way to make it faster? Without having to resort to a parfor loop.

[Walter Roberson]

Vectorize with logical tests.

Or recognize that you can split the code into sections:

for i=1:n
    for j = 1 : i
        j is never greater than n in this case so you do not need to test it
    end
end
for i=n+1:2*n-1
    for j = 1 : n
        j is never greater than n in this case so you do not need to test it
    end
    for j = n+1:i
        j is always greater than n in this case so you do not need to test it
    end
end

Or you could do

for i=1:2*n-1
    temp=zeros(i,2);
    for j=1:i
       if i-j+1>n
         idx2=0;
       else
         idx2=i-j+1;
       end
       temp(j,:)=[j,idx2]
    end
    temp(n+1:end,1) = 0;
    idx{i}=temp;
end

That is, you let j be assigned for the first index always and then later in vectorized form you zap part of it to be 0.