IMG_7275.jpeg

# Algorithmic Complexity ## What Is Algorithmic Complexity? Algorithmic complexity is a measure of how much time (time complexity) and space (space complexity) is required by an algorithm for an input of a given size. - Used to compare the efficiency of different algorithms. - Helps to predict ho...

# Algorithmic Complexity ## What Is Algorithmic Complexity? Algorithmic complexity is a measure of how much time (time complexity) and space (space complexity) is required by an algorithm for an input of a given size. - Used to compare the efficiency of different algorithms. - Helps to predict how well an algorithm will scale as the input size increases. ## How Is Complexity Expressed? Using **Big O notation**: - Describes the upper bound of an algorithm's growth rate. - Focuses on the worst-case scenario. - Ignores constant factors and lower-order terms. **Common Notations**: - O(1): Constant complexity. - O(log n): Logarithmic complexity. - O(n): Linear complexity. - O(n log n): Linearithmic complexity. - O(n^2): Quadratic complexity. - O(2^n): Exponential complexity. - O(n!): Factorial complexity. ## Time Complexity It quantifies the time taken by an algorithm to run as a function of the length of the input. ### Common Time Complexities | Notation | Name | Description | Example | | :------- | :------------ | :---------------------------------------------------------- | :--------------------------- | | O(1) | Constant | Execution time is the same regardless of input size. | Accessing an array element | | O(log n) | Logarithmic | Time increases logarithmically as the input size increases. | Binary search | | O(n) | Linear | Time increases linearly with the input size. | Simple search | | O(n log n)| Linearithmic | More efficient than quadratic algorithms. | Merge sort | | O(n^2) | Quadratic | Time increases quadratically with the input size. | Bubble sort | | O(2^n) | Exponential | Time doubles with each addition to the input size. | Recursive Fibonacci | | O(n!) | Factorial | Time grows factorially with the input size. | Traveling salesman problem | ## Space Complexity It quantifies the amount of memory space taken by an algorithm to run as a function of the length of the input. Includes space for input values and auxiliary space. ### Common Space Complexities | Notation | Description | Example | | :------- | :---------------------------------------------------------- | :--------------------------------------- | | O(1) | Algorithm uses a constant amount of space. | Using a few variables in a loop | | O(n) | Space used increases linearly with the input size. | Creating an array of size *n* | | O(n^2) | Space used increases quadratically with the input size. | Creating a 2D array of size *n x n* | | O(log n) | Space increases logarithmically as the input size increases. | Depth of a recursion stack (e.g. binary tree) | ## Examples ### Example 1: Linear Search - Look for an element in an unsorted array. - Time Complexity: O(n). ```python def linear_search(arr, target): for i in range(len(arr)): if arr[i] == target: return i return -1 ``` ### Example 2: Binary Search - Look for an element in a sorted array. - Time Complexity: O(log n). ```python def binary_search(arr, target): left, right = 0, len(arr) - 1 while left arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] ``` ## Tips to Reduce Complexity - Use appropriate data structures. - Optimize algorithms (e.g., divide and conquer). - Avoid unnecessary calculations. - Utilize caching. - Profile code to identify bottlenecks. ## Conclusion - Understanding algorithmic complexity is crucial for writing efficient code. - Choosing the right algorithm and data structure can significantly impact performance. - Analyzing and optimizing code can lead to substantial improvements in both time and space complexity.