Recap

  • Explain why we use Big-Oh notation.

Algorithm Efficiency: how an algorithm utilizes resources, namely the amount of time it uses.

Random Access Machine or RAM: a hypothetical computer with infinite memory and accessing memory is "free." All basic operations take one step. Loops/functions are the compositions of many single-step operations.

Algorithm Runtime: the number of (RAM) steps as a function of input size. We consider worst-case analysis unless specified otherwise.

It can be difficult to precisely work out the exact number of RAM instructions executed by a program.

We will now introduce the Big-Oh (read it as "big O") notation which allows us to describe the growth rate of functions. The Big-Oh notion makes it easier to compare the runtime of algorithms without having to precisely count the number of (RAM) steps they take.