- O(1) Constant- no loops
- O(log N) Logarithmic- 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 Liniear- 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).
- Operations (+, -, *, /)
- Comparisons (<, >, ==)
- Looping (for, while)
- Outside Function call (function())
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
- Variables
- Data Structures
- Function Call
- Allocations
| Algorithm | Average | Worst case |
|---|---|---|
| Space | O(n) | O(n) |
| Search | O(1) | O(n) |
| Insert | O(1) | O(n) |
| Delete | O(1) | O(n) |
- Singly Linked List
- Circular Linked List
- Doubly Linked List
| Algorithm | Average |
|---|---|
| prepend | O(1) |
| append | O(1) |
| lookup/search | O(n) |
| insert | O(n) |
| delete | O(n) |
| reverse | O(n) |
| Algorithm | Average |
|---|---|
| lookup | O(n) |
| pop | O(1) |
| push | O(1) |
| peek | O(1) |
| Algorithm | Average |
|---|---|
| lookup | O(n) |
| enqueue | O(1) |
| dequeue | O(1) |
| peek | O(1) |
| Algorithm | Average |
|---|---|
| lookup | O(log n) |
| insert | O(log n) |
| delete | O(log n) |