f727120389538843f967378ffa3e43b2.jpeg

# Algorithmic Complexity The measure of how much time (Time Complexity) and space (Space Complexity) an algorithm needs, expressed as a function of the size of the input. **Why do we care?** - Estimates how well an algorithm will perform - Can compare different algorithms **Big-O Notation** Des...

# Algorithmic Complexity The measure of how much time (Time Complexity) and space (Space Complexity) an algorithm needs, expressed as a function of the size of the input. **Why do we care?** - Estimates how well an algorithm will perform - Can compare different algorithms **Big-O Notation** Describes the limiting behavior of a function, when the argument tends towards infinity. - $O(f(n))$ - Describes the **upper bound** of the time/space complexity - Describes the **worst case** scenario - Most common notation **Common complexities** | Name | Notation | Example | | ------------- | ---------- | ----------------------------- | | Constant | O(1) | Accessing any element in array | | Logarithmic | O(log n) | Binary Search | | Linear | O(n) | Linear Search | | Log-Linear | O(n log n) | Merge Sort | | Quadratic | O(n^2) | Bubble Sort | | Cubic | O(n^3) | Matrix Multiplication | | Exponential | O(2^n) | Towers of Hanoi | | Factorial | O(n!) | Travelling Salesman |