IMG_2451.jpeg

# Algorithmic Complexity ## What is complexity? - A measure of the amount of resources required for an algorithm. - Resources can be time (time complexity) or memory (space complexity). - Complexity is expressed using Big O notation, which describes the upper bound of the growth rate of the...

# Algorithmic Complexity ## What is complexity? - A measure of the amount of resources required for an algorithm. - Resources can be time (time complexity) or memory (space complexity). - Complexity is expressed using Big O notation, which describes the upper bound of the growth rate of the resources required as the input size increases. - The size $n$ is a measure of the size of the input. ### Time Complexity The time complexity of an algorithm is the amount of time it takes to run as a function of the size of the input. - **Best Case**: The minimum amount of time an algorithm can take to complete - **Worst Case**: The maximum amount of time an algorithm can take to complete - **Average Case**: The average amount of time an algorithm can take to complete Common time complexities include: | Complexity | Name | | :--------- | :------------ | | $O(1)$ | Constant | | $O(log n)$ | Logarithmic | | $O(n)$ | Linear | | $O(n log n)$ | Log-linear | | $O(n^2)$ | Quadratic | | $O(n^3)$ | Cubic | | $O(2^n)$ | Exponential | | $O(n!)$ | Factorial | ### Space Complexity The space complexity of an algorithm is the amount of memory it uses as a function of the size of the input. - Auxiliary space: extra space used by the algorithm, not including the space used by the input. ## Big O Notation - A way to classify algorithms according to how their running time or space requirements grow as the input size grows. - It focuses on the upper bound of the growth rate, ignoring constant factors and lower-order terms. ### Rules for Big O Notation 1. Only the dominant term is kept. 2. Constant factors are ignored. 3. Big O is always for the worst case. 4. $O(f + g) = O(max(f, g))$ 5. $O(f * g) = O(f) * O(g)$ 6. $O(c * f) = O(f)$, where c is constant 7. $O(c) = O(1)$, where c is constant ## Examples | Algorithm | Time Complexity | Space Complexity | | :----------------- | :-------------- | :--------------- | | Access array | $O(1)$ | $O(1)$ | | Search in array | $O(n)$ | $O(1)$ | | Sort array | $O(n log n)$ | $O(n)$ | | Matrix Multiplication | $O(n^3)$ | $O(n^2)$ | ### Common Data Structure Operations | Data Structure | Operation | Time Complexity | | :------------- | :-------- | :-------------- | | Array | Access | $O(1)$ | | | Search | $O(n)$ | | | Insertion | $O(n)$ | | | Deletion | $O(n)$ | | Linked List | Access | $O(n)$ | | | Search | $O(n)$ | | | Insertion | $O(1)$ | | | Deletion | $O(1)$ | | Stack | Push | $O(1)$ | | | Pop | $O(1)$ | | Queue | Enqueue | $O(1)$ | | | Dequeue | $O(1)$ | | Binary Search Tree | Search | $O(log n)$ | | | Insertion | $O(log n)$ | | | Deletion | $O(log n)$ | | Hash Table | Search | $O(1)$ | | | Insertion | $O(1)$ | | | Deletion | $O(1)$ |