ACO 101 Study Guide - Final Guide: Quadratic Function, Natural Number, Product Rule
Document Summary
So far we have talked about o() informally, as a way of capturing the worst-case computation time of an algorithm. We are now going to delve more in detail into the de nition of o(), as well as how we compute it for different pieces of code. Note that o() is used in general to measure both time as quell as memory requirements. Whenever we assess running time, we will do it as a function of the size of the input provided to the algorithm. We are mainly interested in the shape of the running time, as a function of the. For example, the code: int x = 11; int y = 10; int z = x + y; if (z > 10) z = z 1; is o(1). No matter how we modify the values, these operations will always take the same amount of time.
