Is there a O(n) way to draw a 2-D array grid instead of O(n²) in C?

Question

Is there a O(n) way to draw a 2-D array grid instead of O(n²) in C? For instance, I'm wondering if there's a way to use one for loop instead of two. I always felt like there was a way, but thought I'd turn it over to you...

ARRAY2D grid;

void ShowGrid(void)
{
    int x, y;

    for (y = 0; y < grid.height; y++)
    {
        for (x = 0; x < grid.width; x++)
        {
            printf("%d", arr2_get(&grid, x, y));
        }

        printf("\n");
    }

    printf("\n");
}

Answer 1

You normally study what happens as you increase the number of elements.

If that's the case here, the code you posted is O(N), not O(N²).

If the grid has 100 elements, the number of times printf will be called will be proportional to 100 (O(N)), not proportional to 10,000 (O(N²)).

If on the other handle you were studying what happens as you increase the number of rows or columns, visiting all the elements will be at least O(R*C) since you have R*C elements.

---

Note that you can flatten the two loops, but it doesn't change the complexity in the least:

void ShowGrid()
{
    const int H = grid.height;
    const int W = grid.width;
    int n;

    for (n = 0; n < H*W; ++n)
    {
        int y = n / W;
        int x = n % W;
        printf("%d", arr2_get(&grid, x, y));
        printf("\n") if x == W-1;
    }
}

Answer 2

The following code uses a single for loop:

void ShowGrid(void)
{
    int i;

    for (i = 0; i < grid.width * grid.height; i++)
    {
        int x = i % grid.width;
        int y = i / grid.width;

        printf("%d", arr2_get(&grid, x, y));

        if (x == grid.width - 1)    
            printf("\n");
    }

    printf("\n");
}

Another approach without multiplication or division:

void ShowGrid(void)
{
    int x = 0;
    int y = 0;

    while (y < grid.height) {
        printf("%d", arr2_get(&grid, x, y));
        x += 1;

        if (x == grid.width) {
            printf("\n");
            x = 0;
            y += 1;
        }
    }

    printf("\n");
}

But the time complexity is obviously the same as with two for loops.

Answer 3

There are ways to structure your 2d matrix as a 1 dimensional array or your loop variables, which will allow you to use 1 loop. However, this will not reduce the run time complexity at all.

In your situation, you are always going to have to access each cell of the 2d grid.

If you define N = Width*Height. Your code is already O(n). If you define N = Width = Height, then your code is O(N^2). Neither of these can be improved.