Да, может. Асимптотическая сложность описывает поведение алгоритма при больших n, но не учитывает константы и меньшие члены. На практике при малых n алгоритм с O(n²) может быть быстрее из-за меньших накладных расходов.

Пример:

# Квадратичный алгоритм (вставками)
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

O(nlogn) алгоритм (слиянием)

def merge_sort(arr):
if len(arr) > 1:
mid = len(arr)//2
L = arr[:mid]
R = arr[mid:]
merge_sort(L)
merge_sort(R)
i = j = k = 0
while i < len(L) and j < len(R):
if L[i] < R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
while i < len(L):
arr[k] = L[i]
i += 1
k += 1
while j < len(R):
arr[k] = R[j]
j += 1
k += 1

Для малых массивов (n < 10-20) insertion_sort часто быстрее, несмотря на O(n²), так как merge_sort имеет больше накладных расходов на рекурсию и создание подмассивов.