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 input.