Сочетание логики предикатов с нотой Big O

Question

Истина или ложь? ∀f [f = Ω (n^2) ∧ f = O (n^3) ⇒ f = Θ (n^2) ∨ f = Θ (n^3)]

Answer 1

Нет, утверждение означает, что лучшим случаем является Theta (n^2), а худшим случаем является Theta (n^3). Если это утверждение истинно, это будет означать, что средний случай никогда не может отличаться от лучшего или худшего случая, что неверно.

См., Например, BST, где лучшим случаем является Omega (1), средний случай - O (log n), а наихудший - O (n). (Обратите внимание, что некоторые люди не согласятся со мной и перечисляют O (log n) как лучший случай, но я не согласен с этим).

В этом случае средний случай не должен быть либо Тета (n^2), либо Theta (n^3), поскольку он может быть Theta (n^2 log n), который больше, чем Theta (n^2) и меньше, чем Theta (n^3). Я не могу придумать алгоритм, который на самом деле - это, что небрежно, но вы могли бы хотя бы представить себе алгоритм (хотя и надуманный), который на самом деле есть.