Как доказать комбинацию асимптотических обозначений?

Question

Я думаю, что хорошо понимаю, что означают обозначения Big O, omega и theta и как доказать, является ли функция одной из них. Я не понимаю, как доказать их комбинацию, как в проблеме. Может ли кто-нибудь объяснить это мне?

Θ (n) + O (n ^ 3) = O (n ^ 3)

редактировать: опечатка, первоначально сказал не равно

Answer 1

На самом деле, я думаю, что Θ (n) + O (n ^ 3) = O (n ^ 3).

Если у вас есть функция f с константами k1 и k2 такая, что k1 * n <= f (n) <= k2 * n асимптотически (это Θ), и у вас есть функция g с константой k3 такая, что g (n) < = k3 * n ^ 3 асимптотически (это левый big-O), то существует константа k4 такая, что f(n) + g(n) <= k4*n^3 асимптотически (правый big-O). Просто возьмите k4 = k2 + k3 и ограничитесь n >= 1, потому что если n> = 1, то k2*n + k3*n^3 <= k2*n^3 + k3*n^3 = (k2 + k3)*n^3 = k4*n^3.

Чтобы показать неравенство, подобное тому, которое вы запрашиваете, проще: тогда вам просто нужно показать конкретные f и g, которые защищают границы для левой стороны, но где f (n) + g (n) не удовлетворяет границам для правая сторона.