# Recurrence Relation for Column Major Form of multidimensional array

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?

• Can you figure out the formula with 4 columns? Then 5 columns? Then 6 columns? Then ...? – Apass.Jack Jan 6 at 19:51
• Why is $e_1=,i_1$? Shouldn't it be $i-1$? @Apass.Jack – kauray Jan 6 at 20:41
• Let us start with one dimensional then. Let $A$ be a one-dimensional array, $A[0], A[1], \cdots, A[n_1]$. How many elements are before $A[i_1]$? For example, how many elements are before $A[0]$? before $A[1]$? ... – Apass.Jack Jan 6 at 21:14
• Oh...$i_1$ elements – kauray Jan 6 at 22:07
• I will work it out further and write one – kauray Jan 7 at 14:05