The letter O in big O notation stands for order, in recognition that rates of growth are defined as the order of a function. It measures the worst-case running time complexity, that is, the maximum time to be taken by the algorithm. We say that one function T(n) is a big O of another function, F(n), and we define this as follows:
The function, g(n), of the input size, n, is based on the observation that for all sufficiently large values of n, g(n) is bounded above by a constant multiple of f(n). The objective is to find the smallest rate of growth that is less than or equal to f(n). We only care what happens at higher values of n. The variable n0 represents the threshold below which the rate of growth is not important. The function T(n) represents the tight upper bound F(n). In the following plot, we can see that T(n) = n2 + 500 = O(n2), with C = 2 and n0 being...
