In this blog, we are going to learn about Big-O notation with examples.

Big-O Notation

• This notation has been developed as the standard for comparing algorithm.
• The main aim of this notation is to identify the dominant term in the determining the time complexity of an algorithm.
• Definition: Let f(n) and g(n) be the two functions where n is +ve integer, then we can say that f(n) is of the order g(n),generally written as: f(n)=O(g(n)).
  if and only if there exists a constant c>0 such that.
  |f(n)|<= c|g(n)|for n>=n0, where n0 is an arbitrary large +ve number.

Example 1: This code segment will work in linear time which means for each input you are giving, some “1” amount of operation inside the loop is performed.

for(int i = 0 ; i < n ; i ++) 
{ 
// Do something 
}

• N(no of input) * 1 (No of operation performed for each input) = N
• This is known as O(N).

Example 2:This code segment will work in Quadratic time which means for each input you are giving, “N” amount of operation inside the loop is performed.

for(int i = 0 ; i < n ; i ++) 
{ 
	for(int j = 0 ; j < n ; j ++) 
		{ 
		// Do something 
		} 
} 

• N(no of input) * N (No of operation performed for each input) = N^2
• This is known as O(N^2).

Therefore we can say that big O (n^2) is having higher or bad complexity due to nested loop.

Other Asymptotic Notations

• Big Omega Notation: Big-O notation is used for analyzing the upper bound of the function, the omega notation is used when the function defines a lower bound for the function f(n). It is formally defined as
• If and only if there exists a +ve constant c and n0 such that f(n)>=c.g(n) for n>n0. The definition is read as function f(n) is omega of g(n) if there exists a +ve number c such that f(n) is at least equal to c.g(n) for almost all values of n where n>n0.
• Big –Theta Notation: Theta notation can be described as f(n)=theta g(n)if and only if there exits +ve constant c and n0 such that f(n)=c.g(n) for all n>=n0 . In other words, for large n, g(n) is tight bound for f(n) i.e. g(n) is both lower and upper bound for f(n).

Special Classes of Algorithms

• Logarithmic: O(log n)
• Linear: O(n)
• Quadratic: O(n^2)
• Polynomial: O(n^k), k >= 1
• Exponential: O(a^n), a > 1