Image 12-03-2025 at 19.20.jpeg

# Algorithmic Complexity ## What is Complexity? Complexity is a qualitative attribute concerned with the resources required to perform a computation. Resources include: * **Time** (number of steps) * **Space** (memory/storage) * **Energy** (number of Joules) * **Randomness** (number of r...

# Algorithmic Complexity ## What is Complexity? Complexity is a qualitative attribute concerned with the resources required to perform a computation. Resources include: * **Time** (number of steps) * **Space** (memory/storage) * **Energy** (number of Joules) * **Randomness** (number of random bits) * **Communication** (number of messages) We focus on time and space. Complexity is usually expressed as a function of the input size, $n$. ## What is Algorithmic Complexity? Algorithmic complexity is the measure of resources required by an algorithm as a function of the input size $n$. For time complexity, we count the number of elementary operations performed by the algorithm. Examples of elementary operations include: * assignments * arithmetic operations * comparisons * array accesses * pointer dereferences For space complexity, we count the amount of memory required by the algorithm. This includes memory for the input and output, as well as auxiliary memory used by the algorithm. ## How to measure complexity? There are several ways to measure the complexity of an algorithm: * **Best-case complexity**: the complexity of the algorithm when the input is the most favorable. * **Worst-case complexity**: the complexity of the algorithm when the input is the least favorable. * **Average-case complexity**: the average complexity of the algorithm over all possible inputs. * **Amortized complexity**: the average complexity of a sequence of operations. We usually focus on worst-case complexity. ## Asymptotic Notation Asymptotic notation is a way of describing the limiting behavior of a function. It is used to classify algorithms according to how their running time or space grows as the input size grows. ### Big-O Notation $O(g(n))$ is the set of functions $f(n)$ such that there exist positive constants $c$ and $n_0$ such that $0 \le f(n) \le c \cdot g(n)$ for all $n \ge n_0$. $g(n)$ is an asymptotic upper bound for $f(n)$. ### Big-Omega Notation $\Omega(g(n))$ is the set of functions $f(n)$ such that there exist positive constants $c$ and $n_0$ such that $0 \le c \cdot g(n) \le f(n)$ for all $n \ge n_0$. $g(n)$ is an asymptotic lower bound for $f(n)$. ### Big-Theta Notation $\Theta(g(n))$ is the set of functions $f(n)$ such that there exist positive constants $c_1$, $c_2$, and $n_0$ such that $0 \le c_1 \cdot g(n) \le f(n) \le c_2 \cdot g(n)$ for all $n \ge n_0$. $g(n)$ is an asymptotically tight bound for $f(n)$. ## Common Complexities The following table lists some common complexities in increasing order: | Complexity | Name | Example | | :--------- | :------------ | :----------------------------- | | $O(1)$ | Constant | Accessing an array element | | $O(log n)$ | Logarithmic | Binary search | | $O(n)$ | Linear | Linear search | | $O(n log n)$ | Log-linear | Merge sort | | $O(n^2)$ | Quadratic | Selection sort | | $O(n^3)$ | Cubic | Matrix multiplication | | $O(2^n)$ | Exponential | Brute-force search | | $O(n!)$ | Factorial | Traveling salesman (brute-force) | ## How to determine the complexity of an algorithm? 1. Identify the input size $n$. 2. Identify the basic operations. 3. Determine the number of times the basic operations are executed as a function of $n$. 4. Express the complexity using asymptotic notation. ## Examples ### Example 1 ```python def sum_array(array): sum = 0 for element in array: sum += element return sum ``` The input size is the length of the array, $n$. The basic operation is the addition `sum += element`, which is executed $n$ times. The complexity is $O(n)$. ### Example 2 ```python def sum_matrix(matrix): sum = 0 for i in range(len(matrix)): for j in range(len(matrix)): sum += matrix[i][j] return sum ``` The input size is the number of rows and columns of the matrix, $n$ and $m$ respectively. The basic operation is the addition `sum += matrix[i][j]`, which is executed $n \cdot m$ times. The complexity is $O(n \cdot m)$. If $n = m$, the complexity is $O(n^2)$. ### Example 3 ```python def binary_search(array, target): left = 0 right = len(array) - 1 while left