Search code examples
algorithmcomputation-theory

What does this mean "In the RAM model of computation, instructions are executed one after another with no concurrent operations"


I am going through the book, Introduction To Algorithms, by CLRS. This book uses the RAM model of computation in order to analyze algorithms. When first introducing the model, it says "In the RAM model, instructions are executed one after another, with no concurrent operations". What does it mean? What I understand is that, when the imaginary model processes one instruction, it can't process or listen to the another. For example, when accessing a memory cell, it can't add two numbers. Am I right? If no, then what is the true meaning of that?


Solution

  • Yes, basically you are right. No concurrent operations also means that no two additions can be executed simultaneously (even if the values involved are independent from each other). This is interesting for the runtime. Every operation you write will take one step of time. If there were concurrent operations, then several operations together could be executed at the same time. The calculation of runtime would be more complex, because it would depend on which operations can be executed simultaneously and how many of them the model can really execute at the same time. For the basic treatment, "one operation - one time step" is more convenient.