Introduction to Big O
Big O Notation
Big O is defined as the asymptotic upper limit of a function. In plain english, it means that is a function that cover the maximum values a function could take. As we saw a little earlier this notation help us to predict performance and compare algorithms.
| Growth Rate | Name |
|---|---|
| 1 | Constant |
| log(n) | Logarithmic |
| n | Linear |
| n log(n) | Linearithmic |
| n^2 | Quadratic |
| n^3 | Cubic |
| 2^n | Exponential |
This is kinda abstract let’s see what it means in code:
| Growth Rate | Name | Code Example | description |
|---|---|---|---|
| 1 | Constant | a= b + 1; | statement (one line of code) |
| log(n) | Logarithmic | while(n>1){
n=n/2;
}
| Divide in half (binary search) |
| n | Linear | for(c=0; c<n; c++){
a+=1;
}
| Loop |
| n*log(n) | Linearithmic | Mergesort, Quicksort, … | Effective sorting algorithms |
| n^2 | Quadratic | for(c=0; c<n; c++){
for(i=0; i<n; i++){
a+=1;
}
}
| Double loop |
| n^3 | Cubic | for(c=0; c<n; c++){
for(i=0; i<n; i++){
for(x=0; x<n; x++){
a+=1;
}
}
}
| Triple loop |
| 2^n | Exponential | Trying to braeak a password generating all possible combinations | Exhaustive search |
Superb man!
ReplyDeletethank you!
Delete