IMG_8356.jpeg

# Algorithmic Complexity ## What? Algorithmic complexity is a measure of how much time (time complexity) and memory (space complexity) resources are required by an algorithm for an input of a given size. - The complexity is not the actual amount of time the computer takes to execute the code, but...

# Algorithmic Complexity ## What? Algorithmic complexity is a measure of how much time (time complexity) and memory (space complexity) resources are required by an algorithm for an input of a given size. - The complexity is not the actual amount of time the computer takes to execute the code, but the number of operations performed. - The complexity is most often expressed as a function of the input size $n$. - The complexity is usually estimated in the worst case, i.e., the algorithm's maximum number of operations given an input of size $n$. ## Why? - Allows us to compare the efficiency of different algorithms. - Allows us to predict the performance of an algorithm as the input size grows. - Helps us to choose the best algorithm for a particular problem, based on the size of the input and the resources available. ## How? To determine the complexity of an algorithm, we need to: 1. Identify the input size, $n$. 2. Determine the basic operations performed by the algorithm, i.e., the operations that take a constant amount of time, e.g., arithmetic operations, comparisons, assignments, etc. 3. Count the number of times each basic operation is performed as a function of $n$. 4. Express the complexity using the Big O notation, which ignores constant factors and lower order terms. ## Big O Notation Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. It is used to classify algorithms according to how their running time or space requirements grow as the input size grows. ### Common complexities | Notation | Name | Example | | :---------------- | :------------- | :---------------------------------------------------------- | | $O(1)$ | Constant | Accessing an array element by index | | $O(\log n)$ | Logarithmic | Binary search | | $O(n)$ | Linear | Searching an unsorted array | | $O(n \log n)$ | Log-linear | Merge sort, quicksort | | $O(n^2)$ | Quadratic | Bubble sort, selection sort | | $O(n^3)$ | Cubic | Matrix multiplication | | $O(2^n)$ | Exponential | Traveling salesman problem (brute force approach) | | $O(n!)$ | Factorial | Traveling salesman problem (brute force approach) | | $O(n^n)$ | $n$ to the $n$ | Generating all possible permutations of a string (Brute force) | ### Main rules - Different steps: Add complexities - Loops: Multiply the complexity of the loop by the number of iterations - Conditional statements: The worst-case complexity is the one that occurs in the condition that takes the most time. ## Examples ### Example 1: Constant Time Complexity - $O(1)$ ```python def get_first_element(list): return list ``` The function `get_first_element` takes a list as input and returns the first element of the list. The number of operations performed by this function does not depend on the size of the list. Therefore, the time complexity of this function is $O(1)$. ### Example 2: Linear Time Complexity - $O(n)$ ```python def find_element(list, element): for item in list: if item == element: return True return False ``` The function `find_element` takes a list and an element as input and returns `True` if the element is in the list, and `False` otherwise. The number of operations performed by this function depends on the size of the list. In the worst case, the function will have to iterate through the entire list to find the element. Therefore, the time complexity of this function is $O(n)$. ### Example 3: Quadratic Time Complexity - $O(n^2)$ ```python def bubble_sort(list): n = len(list) for i in range(n): for j in range(n - i - 1): if list[j] > list[j+1]: list[j], list[j+1] = list[j+1], list[j] ``` The function `bubble_sort` takes a list as input and sorts the list using the bubble sort algorithm. The number of operations performed by this function depends on the size of the list. The function has two nested loops, each of which iterates through the list. Therefore, the time complexity of this function is $O(n^2)$.