Зачем нужно Big O notation

Big O notation используется для оценки эффективности алгоритмов, показывая, как их время выполнения или потребление памяти растёт с увеличением размера входных данных. Это помогает сравнивать алгоритмы и выбирать оптимальный для конкретной задачи.

Пример:

# O(n) — линейная сложность  
def linear_search(arr, target):  
    for item in arr:  
        if item == target:  
            return True  
    return False  

# O(n²) — квадратичная сложность  
def bubble_sort(arr):  
    n = len(arr)  
    for i in range(n):  
        for j in range(0, n-i-1):  
            if arr[j] > arr[j+1]:  
                arr[j], arr[j+1] = arr[j+1], arr[j]  

Big O помогает предсказать производительность на больших данных, игнорируя константы и менее значимые члены (например, O(2n + 100) → O(n)).