IMG_3102.jpeg

# Algorithmic Complexity Algorithmic complexity is a measure of the amount of resources (usually time or space) required by an algorithm as a function of the size of the input. It provides a way to compare the efficiency of different algorithms for solving the same problem. **Key Concepts:** *...

# Algorithmic Complexity Algorithmic complexity is a measure of the amount of resources (usually time or space) required by an algorithm as a function of the size of the input. It provides a way to compare the efficiency of different algorithms for solving the same problem. **Key Concepts:** * **Time Complexity:** The amount of time taken by an algorithm to run as a function of the size of the input. * **Space Complexity:** The amount of memory space required by an algorithm to run as a function of the size of the input. * **Big O Notation:** A mathematical notation used to describe the asymptotic behavior of functions. In the context of algorithmic complexity, it describes the upper bound of the time or space complexity of an algorithm. ## Common Time Complexities | Notation | Name | Description | Example | | :------- | :------------ | :-------------------------------------------------------------------------- | :------------------------------------------------ | | O(1) | Constant | The time taken is constant, regardless of the input size. | Accessing an element in an array by index. | | O(log n) | Logarithmic | The time taken increases logarithmically with the input size. | Binary search. | | O(n) | Linear | The time taken increases linearly with the input size. | Searching for an element in an unsorted array. | | O(n log n)| Linearithmic | The time taken increases linearly with the input size multiplied by a log. | Merge sort, quicksort (average case). | | O(n^2) | Quadratic | The time taken increases quadratically with the input size. | Bubble sort, insertion sort. | | O(2^n) | Exponential | The time taken increases exponentially with the input size. | Finding all subsets of a set. | | O(n!) | Factorial | The time taken increases factorially with the input size. | Finding all permutations of a set. | ## How to Determine Algorithmic Complexity 1. **Identify the dominant operations:** Determine the operations that are performed most frequently in the algorithm. 2. **Count the number of times the dominant operations are executed:** Express the number of times the dominant operations are executed as a function of the input size. 3. **Express the function in Big O notation:** Simplify the function by dropping constant factors and lower-order terms. ## Examples ### Example #1: ```python def find_element(arr, element): for i in range(len(arr)): if arr[i] == element: return i return -1 ``` **Time Complexity:** O(n) - Linear time complexity, as the algorithm iterates through each element in the array once in the worst case. ### Example #2: ```python def binary_search(arr, element): low = 0 high = len(arr) - 1 while low