Using while-loops instead of for-loops to create a 2D array for runtime efficiency

Question

I have created the following code in Jana (Java-Based Abstract Notation for Algorithms) which creates a 2-dimensional array of length n:

fillMatrix(↕int matrix[1:n,1:n], ↓int n, ↓int a){

for(i=1…n){
    for(j=1…n){
    if(abs(↓(i-j))<=a){
        matrix[i,j]=1
    }else{
        matrix[i,j]=0
    }
    }
}
}

int abs(↓int i){
    if(i<0)
        return –i
    else
        return i
}

This code has an asymptotic runtime of O(n^2).

My question is, assuming that each element of the matrix is initialized to 0 at the call, how can I make this code more efficient?

Thanks in advance for the help!

Answer 1

Assuming you only have to initialize the cells that get 1 value (the rest of the cells are 0 by default):

If a is much smaller than n, you can initialize the cells that get 1 value in O(n + a*n) time.

For example, if a == 0, all you need is to set the n cells of the main diagonal of the matrix ((0,0),(1,0),...,(n-1,n-1)) to 1.

If a == 1, you need to set the n cells of the main diagonal + the 2*(n-1) cells of the diagonal adjacent to the main diagonal.

...

If a = c, you need to set O(n) + O(2c*n) cells to 1, which is O(n + c*n).

To implement this algorithm, you'll need to replace your O(n^2) loop with 2*a+1 O(n) loops (one loop for each relevant diagonal).