There are three different notations:
- big O - worst case. this is most important because in software engineering we typically plan for the worst case.
- big Theta (Θ) - time complexity is the same for all n
- big Omega (Ω) - best case
- constant O(1)
- logarithmic O(log N)
- linear O(N)
- log linear O(N log N)
- polynomial O(N^X) where X is some constant eg. quadratic O(N^2) and cubic O(N^3)
- exponential O(2^N)
- factorial O(N!)
| Algorithm | Time complexity (Best) | Time complexity (Average) | Time complexity (Worst) | Space complexity |
|---|---|---|---|---|
| Bubble sort | O(n) | O(n^2) | O(n^2) | O(1) |
| Insertion sort | O(n) | O(n^2) | O(n^2) | O(1) |
| Selection sort | O(n^2) | O(n^2) | O(n^2) | O(1) |
| Merge sort | O(nlogn) | O(nlogn) | O(nlogn) | O(n) |
[1]https://www.bigocheatsheet.com
[2]https://bradfieldcs.com/algos/analysis/big-o-notation
[3]https://pythontutor.com/javascript.html#mode=display
[4]https://www.toptal.com/developers/sorting-algorithms
[5]https://visualgo.net/en
To run these examples, just copy the code snippets and paste in Chrome Dev Tools under Snippets and run from there by pressing Cmd + Enter.
Call the function by it's name in the console:
