Why Asymptotoic Notations and Analysis?

When developing code for a software application, we frequently need estimate how the application code consumes resources such as processor, time, and memory and whether the code scales well. It turns out asymptotic notations and analysis can help to answer these questions. The asymptotic notations include Big-O, little-o, Big-Omega, little-omega, and Big-Theta.

Most algorithms handles input whose size affects the time and memory to execute the algorithms. If we use a function f(n), where n is standing for the size of the input, to indicate the cost to execute the algorithm, f(n) is a non-decreasing function, which grows as the input n does. Usually the larger the input n is, the longer the time or the memory is used to execute an algorithm.

Asymptotic notations are usually discussed in theoretical CS courses. For a cost function f(n), Big-O notation is usually used to describe a tight-upper bound for the cost of an algorithm; little-o notation is used to describe an upper bound; Big-Omega notation is used to describe a tight lower bound; little-omega is to describe a lower bound; and Big-Theta is a sandwich between Big-Omega and Big-O, which describes the same order function with the cost function f.

A lot of times we can estimate the order of algorithms using common sense. If an algorithm uses simple loops, the algorithm is in O(n), which increases linearly with respect to the growth of input size n; if the loops are nested, for example, in order to identify a value x in a matrix n*n, a loop is nested within an other loop, the algorithm is in O(n^2); if a search is proceed in an ordered data set organized using a tree structure, the algorithm is O(lgn); if a divide-and-conquer algorithm first partitions the input, and then combine the results, the algorithm is in O(nlgn); and if the algorithm is solving a hard problem such as traveling salesman problem, the algorithm is very possible in O(C^n) where C > 1 is a constant.