We will briefly discuss about the Big-O notations below, starting from  the fastest ( O(1) ) to the slowest  (N! factorial)

1. Constant O(1) : Fastest.  Perform n statement that E.g  If we swap two  elements, then what we do is  the swap  the first thing and thee switch another.

2. Logarithmic  : O(Log(n) : For example, binary search tree, where we are halving the problem each time i.e halving the search problem every time.

3. Linear : O(n) :  Array sort.  Bigger the array the  larger would be the number of steps for swap.  It can be  easily identified as a single for loop.

4. Linear-Log  : N* log(n) :  Merge Sort, where we break the array apart and also do the search.

5. Quadratic O(n^2) :  Can be easily identified as a for loop inside a for loop i.e we will have to loop through the the n-times  inside a structure times(*)  the n number of iterations i.e activities on the outside for loop.

5. Quadratic O(n^2) : Can be easily identified as  triple nested for loop.

6. O(2^n) : Is even more expensive than Quadratic

7. O(N!)- factorial : Extremely expensive

A simple Big-O notation computation example

for() {
for(){
statement
}
}
statement

The Big O notation will be
=  N^2 +1
= O(N^2), because only the biggest coefficient matters

A simple demonstration of how Big-O scales, for N =100

O- notation

Big-O complexity Seconds
O(1) 1
O(Log(n)) 6.64
O(n) 100
N * log(n) 664
O(N2) 10,00
O(N3) 100,000
O(2n) 1267650600228229401496703205376
O(N!) 9.3326215443944152681699238856267e+157
Advertisements