-
-
Save kaidenme/f0dbe89f9c4f5f46e008ff53baab5b1d to your computer and use it in GitHub Desktop.
Big O Notation Cheat Sheet
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| Link: https://www.bigocheatsheet.com/ | |
| #Big O Cheat Sheet: | |
| -Big Os- | |
| O(1) Constant | |
| - no loops | |
| O(log N) Logarithmic | |
| Reference: https://hackernoon.com/what-does-the-time-complexity-o-log-n-actually-mean-45f94bb5bfbf | |
| - usually searching algorithms have log n if they are sorted (Binary Search) | |
| O(n) Linear | |
| - for loops, while loops through n items | |
| O(n log(n)) Log Linear | |
| - usually sorting operations | |
| O(n^2) Quadratic | |
| - every element in a collection needs to be compared to ever other element. | |
| - Two nested loops | |
| O(2^n) Exponential | |
| - recursive algorithms that solves a problem of size N | |
| O(n!) Factorial | |
| - you are adding a loop for every element | |
| Iterating through half a collection is still O(n) | |
| Two separate collections: O(a * b) | |
| -What can cause time in a function?- | |
| Operations (+, -, *, /) | |
| Comparisons (<, >, ==) | |
| Looping (for, while) | |
| Outside Function call (function()) | |
| -Rule Book- | |
| Rule 1: Always worst Case | |
| Rule 2: Remove Constants | |
| Rule 3: Different inputs should have different variables. O(a+b). A and B arrays nested would be | |
| O(a*b) | |
| + for steps in order | |
| * for nested steps | |
| Rule 4: Drop Non-dominant terms | |
| -What causes Space complexity?- | |
| Variables | |
| Data Structures | |
| Function Call | |
| Allocations |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment