In order to judge the performance of an algorithm, there exists a mental mathematical model. This mental mathematical model helps us to ensure the stability and high performance of algorithms. Also, one could compare two algorithms using this model.
Mathematical Model: Random Access Machine.
This model consists of a processor and memory.
Designing algorithms for RAM:
- Variable names are allowed
- Arrays, structures will be taken as Primitive data types
- Trees, lists etc are allowed.
- Instruction set:
1. Arithmetic and Logical Operations (Single Step)
2. Jumps and conditional jumps (Single Step)
3. Pointer instructions (Single Step)
4. Single dimension Array Operations (Single Step)
Lets consider a 2D array. To represent the 2D array in memory, one needs to use a linear model as the memory is linear in nature.
thus, A[i, j] = A’[i * m + j] , where m is the number of columns in one row of 2D array.
As, A = 1, 2, 3, 4
5, 6, 7, 8
is represented as 1, 2, 3, 4, 5, 6, 7, 8 in the linear memory.
Similarly, for a 3D array A[m][n][o]. A[i, j, k] = A’[(i * (n * o)) + (j * o) + k]
Just try and imagine a stack of 2D arrays, where i represents the number of 2D array in stack, j represents the row number and o represents the column number; and you’ll hit an epiphany.