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
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
|N * log(n)||664|