RAM Model

---

Efficiency here means how an algorithm utilizes resources, namely the amount of time (and space) it uses. Moreover, we want to know how its resource consumption will scale with increasing input size.

RAM: A hypothetical computer

Study algorithms independently of the programming language to allow us to compare algorithms.

Random Access Memory, or RAM, is a model of computation where we:

• assume we have unlimited memory
• access memory for free (variable declaration, value look up, array element access, invoking methods).
• consider simple operations to take one step
• consider loops to be complex operations.
• Account the metod's time steps.

Measure algorithm runtime by counting the number of steps itt akes on a given problem instance under the RAM model of computation.

Example step count

int count = 0; // 1
for (int i = 0; i < 10; i++) {  // 1 + 11 + 10
	for (int j = 0; j < 5; j++) { // (1 + 6 +5) *10
		count++; // (1) * 5 * 10
	} 
} 
System.out.println(count); // 1

We focus on worse case when measuring performance. It is hard to count precisely, so we describe the running time in erms of the upper and lower bounds.