What do you know about algorithm complexity?

Algorithm complexity estimates the amount of computational resources (time and memory) required to execute an algorithm depending on the size of the input data. The most common is time complexity, which describes the number of operations performed by the algorithm.

Big O notation is used to describe the upper bound of the growth of complexity.

Main complexity classes:

O(1) - Constant complexity. Execution time does not depend on the size of the input data.
O(log n) - Logarithmic complexity. Execution time grows slowly with increasing input size (e.g., binary search).
O(n) - Linear complexity. Execution time is directly proportional to the size of the input data.
O(n log n) - Linear-logarithmic complexity. Characteristic of efficient sorting algorithms (e.g., Merge Sort, Quick Sort).
O(n^2) - Polynomial complexity. Execution time grows quadratically (e.g., simple sorting algorithms like Bubble Sort).
O(2^n) - Exponential complexity. Execution time grows very rapidly, unacceptable for large n (e.g., some naive solutions to the traveling salesman problem).

When analyzing complexity:

Constant factors and lower order terms are ignored, as the asymptotic growth at large n is important.
Three cases are considered: best (rarely), average (often), and worst (most important for performance guarantees).

Example: Searching for an element in a list.

# O(n) - linear search, in the worst case, the entire list must be traversed
def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

# O(log n) - binary search, only for sorted lists
def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

Understanding algorithm complexity allows choosing the most efficient solutions for specific tasks, especially when working with large volumes of data.