 Solution

Computational complexity theory studies the resources needed by an algorithm as a function of input size, after specifying the resource and computational model. For example, time complexity may count comparisons, and space complexity may count stored words. Worst-case time complexity $T(n)$ is the greatest cost among inputs of size $n$; best-case and average costs are different measures.

An upper bound guarantees that a cost is no greater than the stated bound. A lower bound guarantees that it is no smaller. For a problem, an algorithm can establish an upper bound on what is achievable, while a problem lower bound must apply to every eligible algorithm in the chosen model. Bounds need not be tight. Concisely,