Что такое Big O?
Короткий ответ
Big O описывает верхнюю оценку роста затрат алгоритма при увеличении входа. Например, O(n) означает линейную оценку, O(n²) - квадратичную.
Разбор
Один проход по массиву обычно дает O(n), проверка всех пар - O(n²). Два последовательных прохода все еще дают O(n): постоянный множитель в такой записи опускают.
Big O не показывает миллисекунды и само по себе не означает худший случай: вид оценки уточняют отдельно. На небольшом входе простой алгоритм иногда быстрее более сложного с лучшей асимптотикой.