Big O Notation

Big O Notation

This notation has been implemented to analyze the worse case of an algorithm. “N” is the number of input elements or amount of tasks and assignments to be done.

 

O(1) Constant Time

This concerns only assignment operations which consume the lowest time take place

String name ="Java";

O (n) Linear

“N” is the amount of input elements. In this scenario the amount of time being consumed, depends on “N”. Loop are the proper example for this case

for(int i=0; i<N; i++){
   name =””+i;
}

Here the assignment in the loop is O(1), but this operation will be repeated N times, then the time complexity is O(n) > O(1)

O(log n) Logarithmic

Here in this situation input elements and time duration go along logarithmically and it’s assumed that it will take up less time than O(n). For instance if we think of amount of input elements as 100, the time complexity of O(n) depends on 100, since log 100 = 2, O(log n) depends on 2. An ideal example is Binary search. Array Literal values in binary search is in order, in the event of a search through in each try, half of remaining will be added. The time complexity is O(n)> O(log n) > O(1)

O(n log n) Log Linear

Assuming similar examples from previous cases, if we think of amount of input elements as 100, and n=100, and the time complexity of O(n) depends on 100, and since log 100 = 2, here O(n log n) 100*2=200. This is to approach the way of splitting a problem to subsidiaries and resolving them individually. After all this process, it is to gather all resolved subsidiaries together. This can be seen in merge sort, quick sort, heap sort etc. The comparison is now as follows O(n log n) > O(n) > O(log n) > O(1).

O(n² – n^2) Quadratic

Used when the time complexity depends on n * n. This can be seen in cascade loops, when two elapse n*n. If the amount of loops increases, i will be O(n³) because it relies on n*n*n. This can be seen in Selection sort, insertion sort, quick sort(worst case) etc. The time complexity comparison is O(n²) > O(n log n) > O(n) > O(log n) > O(1)

O(ncformula – 2^n) Exponential

Depending on the number of input elements, the process is slower twice and they are not practical. This is to find the exact solution to the traveling salesman problem.

Resources

http://bigocheatsheet.com/

Leave a Reply

Your email address will not be published. Required fields are marked *