Recurrence Relation for Array

Question

A two dimensional array is stored in column major form in memory if the elements are stored in the following sequence $$A[0][0] A[1][0] A[2][0]...A[n_1-1][0] ... A[0][1] A[1][1] ... A[n_1-1][1] .... A[0][n_2-1]...A[n_1-1][n_2-1]$$

The left most index varies most rapidly if we look at the looping changes.

For a particular element $A[i_1][i_2]...[i_m]$ of an $m$ dimensional array $A[n_1][n_2]...[n_m]$ if we denote $e_m$ as the number of elements stored in memory before the given element, we can see the following

$$ e_1 = i_1$$
$$ e_2 = i_1 + i_2 \times n_1$$
$$ e_3 = i_1 + i_2 \times n_1 + i_3 \times n_1 \times n_2$$

How to show that generally

$$ e_m = e_{m-1} + i_m \times \prod_{j=1}^{m-1}{n_j}$$

If we look at the two dimensional array, the number of elements stored before a particular array location can be calculated as the column number of the element we are looking for summing with the $row \times column$ number of elements. How does the above recurrence relation work?

Comments

@kauray

particular array location can be calculated as the column number of the element we are looking for summing with the row×column number of elements.

You mean A[i][j]=B +size(j + #rows x column no.).. ?

For column major don't we do like,

Address(A[i][j])=B +size(i + #rows x column no.)

Elaborately,

$Address(A[i_1][i_2])=B +size( (i_1-L_r) + (U_r-L_r+1)(i_2-L_c))$

$L_c:$ Lower index of column

$U_r:$ Lower index of row

$L_r:$ Lower index of row

here, $L_c=L_r:=0$

$(U_r-L_r+1)=n1$

$(U_r-L_r+1)=n2$

Here we aren't going to calculate the address. We only want the number of elements so put size=1 and B=0

$e_2=A[i_2][i_3]=( i_2 + n1*i_3)$

For 3-D,

For visualization : https://gateoverflow.in/195348/multidimensional-aaray?show=195362#a195362

[The link shows row major]

A[h][i][j]=( (h- $L_h$)*#rows*#columns + (i) + j*n1)

$e3=A[i_1][i_2][i_3]=(i_1*n1*n2+ i_2 + i_3*n1)=e_2+i_1*n1*n2$