IMG_0654.jpeg

# Algorithmic Complexity ## What? * A measure of how much of a resource (usually time or memory) is needed for an algorithm. * Expressed as a function of the size of the input. * Allows algorithms to be compared independently of implementation and hardware. ## Why? * To predict the resourc...

# Algorithmic Complexity ## What? * A measure of how much of a resource (usually time or memory) is needed for an algorithm. * Expressed as a function of the size of the input. * Allows algorithms to be compared independently of implementation and hardware. ## Why? * To predict the resources required to run an algorithm without implementing it. * To compare the efficiency of different algorithms. * To choose the best algorithm for a given problem. ## How? ### 1. Count the operations * Identify the operations that contribute to the algorithm's execution time. * Count how many times each operation is executed as a function of the input size ($n$). * Simplify the expression by ignoring constants and lower-order terms. ### 2. Express as a function of input size ($n$) **Example** ```python def sum_list(L): sum = 0 # 1 assignment for x in L: # n iterations sum += x # 1 addition and 1 assignment return sum # 1 return ``` $T(n) = 1 + n * 2 + 1 = 2n + 2$ ### 3. Simplify using "Big O" notation * Big O notation describes the upper bound of the algorithm's complexity. * Ignore constants: $O(2n) = O(n)$ * Ignore lower-order terms: $O(n + log(n)) = O(n)$ ## Common Complexities | Complexity | Name | When to use it | | :--------- | :------------ | :-------------------------------------------------- | | $O(1)$ | Constant | When the time is independent of the input. | | $O(log n)$ | Logarithmic | When the time is proportional to the logarithm of n. | | $O(n)$ | Linear | When the time is proportional to the input. | | $O(n log n)$ | "Linearithmic"| When the time is proportional to n times log n. | | $O(n^2)$ | Quadratic | When the time is proportional to the square of n. | | $O(2^n)$ | Exponential | When the time is proportional to a constant to the power of n. | ## Example ### Problem: Find the maximum value in a list. **Algorithm 1:** Iterate through the list and keep track of the maximum value seen so far. ```python def find_max(L): max_value = L # 1 assignment for x in L: # n iterations if x > max_value: # 1 comparison max_value = x # 1 assignment (worst case) return max_value # 1 return ``` $T(n) = 1 + n * 1 + 1 = n + 2 = O(n)$ **Algorithm 2:** Sort the list and return the last element. ```python def find_max_sorted(L): L.sort() # O(n log n) return L[-1] # 1 return ``` $T(n) = n \log n + 1 = O(n \log n)$ **Conclusion:** Algorithm 1 has a lower complexity and is more efficient. *** The image is of a presentation slide that discusses Algorithmic Complexity, including "What?", "Why?" and "How?" to determine it. It also provides some common complexities in table format, going from $O(1)$ to $O(2^n)$. Finally, it gives an example of how to find the maximum value in a list. It provides two algorithms, one with $O(n)$ complexity and another with $O(n \log n)$ complexity for solving the problem.