Нет. Утверждение, что алгоритм имеет размер O (n²), означает, что существует по крайней мере случай, когда алгоритм будет принимать квадратичное c количество операций для завершения sh.
В алгоритме O (n), наихудший случай будет линейным, поэтому для достаточно большого входа в наихудшем случае алгоритма O (n²) всегда потребуется больше операций, чем алгоритма O (n).
O(n) = k * n + a
O(n²) = k2 * n² + k1 * n + b
so we wanna prove that there is a case that O(n) < O(n²)
k * n + a < k2 * n² + k1 * n + b
(k - k1) * n + (a - b) < k2 * n²
(k - k1) / k2 + (a - b) / (k2 * n) < n
Мы видим, что , по мере роста n константы в левой части останутся такими же или уменьшатся, поэтому будет точка, где O (n)