Intro
This is a great summary sheet: Big O Cheat sheet
BigO is a notation that describes how an algorithm performs, by measuring execution time and space efficiency, aka Time & Space Complexity. #TimeComplextity is how long an algorithm takes to produce the expected result. #SpaceComplexity refers to how much memory an algorithm needs to run.
This is done by taking the basic operation count into consideration. BasicOperationCount refers to the number of ‘significant’ steps executed in an algorithm, the ones that carry weight.
As an algorithm’s input size grows so will the number of steps required for it to produce the expected result.
An example. When iterating over an array of n elements, this operation is a O(n) operation due to the need to iterate over n elements… Therefore it scales Linearly as n grows.
Of course not everything grows linearly and there’s a rating of how bad or good an algorithms Big O is:
| Complexity | Big O | Rating |
|---|---|---|
| Constant non-reliant on n | O(1) | BEST |
| Logarithmic | O(log n) | Very good |
| Linear, runs n times | O(n) | okay |
| O(n log n) | Not so good | |
| Quadratic | O(n^2) | Bad |
| Exponential | O(2^n) | Very Bad |
| Factorial | O(n!) | DISGUSTING |
