How to evaluate the complexity of an algorithm or…

Asymptotic analysis is used to evaluate the complexity of algorithms, describing their efficiency depending on input size ($n$). The main steps are:

Defining basic operations: Operations whose execution time significantly depends on $n$ (e.g., comparisons, assignments, arithmetic operations).
Counting the number of operations: Calculating the number of basic operations as a function of $n$, which can be an exact formula or an estimate.
Determining the asymptotic class: Using Big O ($O$), Omega ($\Omega$), and Theta ($\Theta$) notation to describe the upper, lower, and tight bounds of the algorithm's behavior.
- $O(f(n))$: The algorithm runs in time not exceeding a constant times $f(n)$ for large $n$, describing the worst-case scenario.
- $\Omega(f(n))$: The algorithm runs in time at least a constant times $f(n)$ for large $n$, describing the best-case scenario.
- $\Theta(f(n))$: The algorithm runs in time proportional to $f(n)$ for large $n$, describing the average case or when best and worst cases have the same asymptotic order.

The most common is Big O notation for the upper bound of execution time, which is important for understanding the scalability of the algorithm in the worst-case scenario.

Ignoring constants and lower-order terms: When defining asymptotics, constant factors and lower-order terms are ignored because, for large $n$, the function with the highest order dominates. For example, for $3n^2 + 5n + 10$, the asymptotic complexity is $O(n^2)$.

Typical asymptotic classes (in order of increasing complexity):

$O(1)$: Constant time.
$O(\log n)$: Logarithmic time.
$O(n)$: Linear time.
$O(n \log n)$: Linearithmic time.
$O(n^2)$: Quadratic time.
$O(n^c)$ for $c > 1$: Polynomial time.
$O(c^n)$ for $c > 1$: Exponential time.
$O(n!)$: Factorial time.

For analyzing cyclic structures:

Sequential code blocks: Sum their complexities, $O(A+B) = O(\max(A, B))$.
Nested loops: Multiply the number of iterations, e.g., a loop with $n$ iterations inside another with $m$ iterations has complexity $O(n \times m)$. If $m=n$, then $O(n^2)$.
Loops reducing input size: For example, dividing by 2 each iteration leads to logarithmic complexity ($O(\log n)$).

Example:

Simple array traversal:

# Recounting basic operations (comparisons, assignments)
def find_max(arr):
    if not arr:
        return None
    max_val = arr[0]  # 1 assignment
    for i in range(1, len(arr)): # Loop runs n-1 times
        # Inside loop:
        # 1 comparison
        # potentially 1 assignment
        if arr[i] > max_val:
            max_val = arr[i]
    return max_val

If array size is $n = \texttt{len(arr)}$, the loop runs $n-1$ times. Each iteration performs a constant number of operations. Total operations are proportional to $n$. Asymptotic complexity: $O(n)$.

Example: Insertion Sort

# Recounting basic operations
# Main operations: comparisons and assignments/movements

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

The outer loop runs $n-1$ times. The inner loop, in the worst case (array sorted in reverse order), runs approximately $i$ times for each $i$. The total number of operations in the inner loop over all iterations is about $n^2/2$. Asymptotic complexity: $O(n^2)$ in the worst and average cases, $O(n)$ in the best case (already sorted array). When estimating complexity, the worst case (Big O) is usually considered.

How to evaluate the complexity of an algorithm or determine its asymptotic behavior?