Вычитание действительно в большой O-нотации?

Question

Если у нас есть f(n)=O(g(n)) и h(n)=O(x(n)), то верно ли, что f(n)-h(n)=O(g(n)-x(n))?

Я так не думаю, потому что неравенство в определении нотации O переворачивается при вычитании x(n) из g(n), то есть; поскольку f(n)<=c_1g(n) для некоторой константы c_1 и h(n)<=c_2x(n) для другой константы c_2, неясно, можем ли мы непосредственно вычитать члены. Есть намеки? Заранее спасибо.

Answer 1

Вы правы. f(n) означает O(g(n)), а h(n) означает O(x(n)), не означает, что f(n)-h(n) означает O(g(n)-x(n)).

В качестве контрпримера просто возьмите g(n) = x(n) = 1 и f(n) = 2 и h(n) = 1. Это явно удовлетворяет предположениям, но f(n)-h(n) = 1, тогда как g(n)-x(n) = 0 и, следовательно, претензия не выполняется.

Единственное, что вы можете сказать о разнице, это то, что она O(max(|h(n)|, |x(n)|)).

Обратите внимание, что то же самое верно для сложения, если вы разрешаете отрицательные значения для функций. В контексте программирования обычно предполагается, что функция принимает только положительные значения, и в этом случае вычитание имеет только частичный смысл.