We have to think about how much time and how much space an algorithm will use as the size of its input(s) increases.

Many problems involve searching through a large number of possibilities, and the algorithm is supposed to find a solution more quickly than just searching through all theoretical possibilities. A basic definition of efficiency is as follows: “An algorithm is efficient if, when implemented, it runs quickly on real input instances.” This obviously leads to questions like how fast is “quickly” and how do we define “real input instances”, especially if the data set could be scaled up significantly. Worst-case running time is the longest possible running time of an algorithm and generally provides a good reference as to the efficiency of the algorithm, even though some specific algorithms may almost never reach their longest possible running time. With polynomial time algorithms, an increase in input size should increase the runtime by some constant factor.

The worst-case performance of an algorithm can be expressed as a function of the size of the inputs. The algorithms in the book will be written in pseudo-code so that when we count the number of steps, we are not actually counting the number of operations on the CPU. I think that could be architecture-dependent. The upper bound of of the running time of an algorithm is a constant multiple of its highest-order term (or an even higher order term). The lower bound of the running time of an algorithm is a constant multiple of its higher-order term or one of lower order. A tight bound occurs when we choose the highest order term of the polynomial, instead of a higher order for an upper bound or a lower order for a lower bound.