RAM model of Computation

After reading this chapter and engaging in the embedded activities and reflections, you should be able to:

• Describe what is meant by efficiency of algorithms.
• Explain the purpose of using the RAM model of computation for analysis of algorithms.
• Identify what counts as a "step" in an algorithm.
• Explain how algorithm runtime is calculated under the RAM model of computation.
• Describe runtime by counting up the number of RAM instructions for a given code snippet.
• Recognize the importance of input size on evaluating algorithm efficiency.
• Know that what we choose to call the size of an input can vary from problem to problem.
• Differentiate between the best-case vs the worst-case analysis.
• Explain why we focus on worst-case analysis.
• Express the number of steps for a given code segment as a function of the input size in the worst case scenario.
• Appreciate that counting the exact number of RAM instructions can be very difficult to work out precisely.