Notion of order of complexity in C Language

Asymptotic Notation

Asymptotic complexity is a way of expressing the cost of an algorithm using idealized units of computational work.

In order to choose the best algorithm for a task many factors, like how long will it take for an algorithm to run or how much memory will be taken by the algorithm during running, has to be considered.

Asymptotic notation is a way of estimating the cost of an algorithm. The main goal of asymptotic notations is to remove complexity from the algorithm and facilitate easy analysis of the algorithm.

Big-O Notation

The Big-O notation measures efficiency based on the time it takes for the algorithm to run as the function of the input size, i.e. the parameter required by the function. It is an upper bound function.

Big-O Notation (O) may be denoted by the following expression:
O(g(n)) = { f(n) : there exist positive constants c and n0 such that 0 < f(n) < c*g(n) for all n > n0 }.

Big Omega Notation

The Big-Omega notation is similar to Big-O notation except that it is a lower bound function. It describes the best that can happen for a given data size.

Omega Notation may be denoted by the following expression:
omega (g (n)) = { f(n) : there exist positive constants c and n0 such that 0 < c * g(n) < f(n) for all n > n0 }

Theta Notation

The Theta notation denotes that the function f(n) is bounded by the function g(n) from both the top and bottom.

Theta Notation may be denoted by the following expression:
theta(g(n)) = { f(n) : there exist positive constants c1 and c2 and n0 such that 0 < c1 * g(n) < f(n) < c2 * g(n) for all n > n0 }

Little o Notation

The Little o Notation represents a loose bounding version of Big-O. The function g(n) bounds from the top of function f(n) but not the bottom.

Little oh Notation (o) may be denoted by the following expression:
o(g(n)) = { f(n) : for any positive constant c>0 , there exists a constant n0 such that 0 < f(n) < c * g(n) for all n > n0 }

Little omega Notation

The Little omega Notation represents a loose bounding version of Big-Omega. The function g(n) bounds from the bottom of the function f(n) but not the top.

Little omega Notation (w) may be denoted by the following expression:
w(g(n)) = { f(n) : for any positive constant c>0 , there exists a constant n0 such that 0 < c * g (n) < f(n) for all n > n0 }

Big-O Notation

Any problem associated with computer science generally has more than one solution. These solutions come in the form of algorithms. It is necessary to find the efficiency of the algorithms so that the best algorithm may be adapted as the solution. The Big-O notation provides a basis for measuring the efficiency of the algorithm.

The Big-O notation measures efficiency based on the time it takes for the algorithm to run as the function of the input size, i.e. the parameter required by the function.

Big-O Notation (O) may be denoted by the following expression:
O(g(n)) = { f(n) : there exist positive constants c and n0 such that 0 < f(n) < c*g(n) for all n > n0 }.

The utility of Big-O notation may be best explained by considering two different algorithms performing the same task. The task to be performed is to find the largest element in the array provided by the user.

c language tutorial learn c language study c language