Big O notation is a theoretical measurement of the execution of an algorithm. It considers time, memory, and problem size. It helps to analysis the programming code with different types of performance i.e. best case, average case, and worst case analysis. Big O measure of asymptotic complexity. The complexity analysis helps to measure the performance of any algorithm irrespective of input size.

## Algorithm performance

Algorithms efficiency described in terms of Time and Space. The time efficiency calculated using CPU utilization. The Space efficiency calculated using memory and disk usage of an algorithm. The developer should know the difference between Performance and complexity. The complexity analysis does not depend on any computer resource. It may change based on the input size. The algorithm performance is machine independent and does not depend on any other factors.

If the algorithm takes N number of elements and executes the statement, the following table explains the running time.

PerformanceNameDescription

O(1) | Constant | Does not depend on the size of the input |

O(log(N)) | Logarithmic | Commonly found in operations on binary trees |

O(N) | Linear | Running time increases linearly with the size of the input |

O(N log(N)) | Super-linear | Not allowed prior assumptions on the input |

O(N^2) | Quadratic | Comparison-based sorting algorithms are quadratic |

O(N^3) | Cubic | Naive multiplication of two N×N matrices |

O(N^c) | Polynomial | Polynomial expression in the size of the input for the algorithm |

O(C^N) | Exponential | Exponential time algorithms on a deterministic Turing machine form the complexity |

O(N!) | Factorial | All the permutation of a list |

Algorithms analysis should be based on machine-independent manner. The RAM model is the memory model analysis which measure the run time by counting the number of steps involved for computing the algorithm. It may be different based on a number of input size. But, the algorithm analysis does not deepened on computers.

The worst case analysis helps the algorithm behavior in worst case scenario and helpful to understand the algorithm performance. Big-oh notation simplifies the algorithm analysis by providing the simple questions to understand the algorithm performance easily. The big o notation simplifies the comparison of algorithms.

N! >> C^N >> N^3 >> N^2 >> N log N >> N >> log N >> 1

## Analysis Types

The algorithm complexity can be best, average or worst case analysis. The algorithm analysis can be expressed using Big O notation. Best, worst, and average cases of a given algorithm express what the resource usage is at least, at most and on average, respectively.

### Best case

Best-case performance used in computer science to describe an algorithm’s behavior under optimal conditions. Example Sort the array of items which already sorted

### Worst case

Worst case performance used to analysis the algorithm behavior under worst case input and least possible to solve the problem. It determines when the algorithm will perform worst for the given inputs. Example Sort the array of items which sorted in reverse order

### Average case

Average case performance measured using the average optimal conditions to solve the problem. Example Sort partially sorted items using Insertion sort

## Amortized analysis

Amortized analysis is a method for analyzing a given algorithm’s time complexity. It analysis resources usage including time and memory in the context of computer programs. Amortized worst-case provide a guaranteed upper limit on the running time. It examines how an algorithm will perform in practice or on average. The amortized cost of N operations is the total cost of the operations divided by N. If the developer push or pop operations on the stack, it takes the O(1) cost. If the stack is full, the stack doubles the array size, copy the old elements to new array takes a lot of costs. The developer can “amortize” the cost over the previous cheap operations.

## Determine complexities

The algorithm complexity ignores the constant value in algorithm analysis. If the algorithm takes, n^2+12n+45 time to calculate all the steps, the algorithm analysis ignores all the constant and takes only O(n^2).

#### Simple statement

The simple statement takes O(1) time.

int x= n + 12;

#### if condition

The best case O(1), worst case O(n)

if( n> 12) { … }else{ .. .. }

#### for/while loops

The loops take N time to complete and take O(n).

for(int i=0;i<n;i++) { .. .. }

#### Nested loops

If the nested loops contain M and N size, the cost is O(MN)

for(int i=0;i<n;i++) { for(int i=0;i<m;i++){ .. .. } }

## Example 1

O(N)

for(int i = 0; i < n; i++) sum++;

## Example 2

O(N)

for(int i = 0; i < n; i+=2) sum++;

## Example 3

O(N^2)

for(int i = 0; i < n; i++) for( int j = 0; j < n; j++) sum++;

## Example 4

O(N)

for(int i = 0; i < n; i+=2) sum++; for(int j = 0; j < n; j++) sum++;

## Example 5

O(n^3)

for(int i = 0; i < n; i++) for( int j = 0; j < n * n; j++) sum++;

## Example 6

O(N^2)

for(int i = 0; i < n; i++) for( int j = 0; j < i; j++) sum++;

## Example 7

O(n^5)

for(int i = 0; i < n; i++) for( int j = 0; j < n * n; j++) for(int k = 0; k < j; k++) sum++;

## Example 8

O(log(n))

for(int i = 1; i < n; i = i * 2) sum++;

## Example 9

log(n)

while(n>1){ n=n/2; }

## Example 10

nlog(n)

void partition(int arr[],int low,int high){ int mid; if(low < high){ mid=(low+high)/2; partition(arr,low,mid); partition(arr,mid+1,high); mergeSort(arr,low,mid,high); } } void mergeSort(int arr[],int low,int mid,int high){ int i,m,k,l,temp[MAX]; l=low; i=low; m=mid+1; while((l <= mid)&&( m <= high)){ if(arr[l] <= arr[m]){ temp[i]=arr[l]; l++; } else{ temp[i]=arr[m]; m++; } i++; } if(l>mid){ for(k=m;k <= high;k++){ temp[i]=arr[k]; i++; } } else{ for(k=l;k <= mid;k++){ temp[i]=arr[k]; i++; } } for(k=low;k <= high;k++){ arr[k]=temp[k]; } }

## Example 11

O(n^3)

for(c = 0; c < n; c++){ for(i = 0; i < n; i++){ for(x = 0; x < n; x++){ a+=1; } } }

If the candidate is preparing for algorithm interview, they should understand the algorithm analysis. If the interviewer asks about any problem which involve data structure and algorithm, they expect the candidate analysis the code based on complexity analysis. So, the candidate must understand the algorithm in terms of best, average and worst case algorithm analysis.

## Leave a Reply

2 Comments on "Algorithm Analysis using Big O notation"

You must be logged in to post a comment.

You must be logged in to post a comment.

Simple and clear explanation. Its really helps the beginners to understand the concept easily.

http://www.gofpatterns.com/design-patterns/module2/big-O-notation.php