Before you look at the solution I have to clear up some confusion.

If we are talking about the lowest bound it takes for the program to complete, then it is O(N^2), because you have to evaluate each table cell no matter what and print the value. This is also considering that by N we denote the side of the table.

On the other hand, the function that takes in i and j and spits out the correct number in O(1) **is possible** without any lookup, which can be also be parallelized and be ported as fragment shader. You can see it below, it's the `eval` function and all calls are independent of their neighbors.

The core challenge is to figure out how to calculate which diagonal are you on -- I call it level -- and what is your local index on that diagonal line. For example, for N=3, we have:
4 2 1
7 5 3
9 8 6

where, "1" is on the first level, "2,3" are on the second level, "4,5,6" are on the third level and so on. Furthermore, 6 is the third number on that line.


```cpp
#include <stdio.h>

int abs( int x )
{
    return x >= 0 ? x : -x;
}

int sum( int n )
{
    return ( n + 1 ) * n / 2;
}

static int n;
static int totalLevels;
static int topRight[2];

int eval(int i, int j)
{
    const int level = abs( topRight[ 0 ] - i ) + abs( topRight[ 1 ] - j );
    if( level < n )
    {
        const int origin = n - 1 - level;
        const int index = i - origin;
        return 1 + sum( level ) + index;
    }
    else
    {
        const int index = i;
        return 1 + n * n - sum( totalLevels - level ) + index;
    }
}

int main()
{
    scanf("%d", &n);
    totalLevels = n * 2 - 1;

    topRight[0] = n - 1;
    topRight[1] = 0;

    for( int j = 0; j < n; ++j )
    {
        for( int i = 0; i < n; ++i )
            printf("%d ", eval( i,j ));

        printf("\n");
    }

    return 0;
}
```