Você pode operar e tirar conclusões sobre as funções descritas assintoticamente?

Esta pergunta é baseada em trabalhos de casa (embora não esteja usando o problema real)!

Digamos que você tenha uma função descrita como:

Você pode então tratar isso como:

e executa matemática nela e mantém seu significado assintótico?

No caso acima, eu poderia conjeturar que $f(n) \in O(2n^2)$ implica $f(n) / 2 \in O(n^2)$ (supondo que os coeficientes sejam importantes neste exemplo)?

Para algumas operações, como adição, multiplicação, você pode operar diretamente na notação assintótica. Por exemplo, se$\small g(n) = \mathcal{O}(n^2)$ e $\small f(n) = \mathcal{O}(n^2)$, então $\small g(n) + f(n) = \mathcal{O}(n^2)$ e $\small g(n) \cdot f(n) = \mathcal{O}(n^4)$. Para algumas outras operações, como divisão, depende então. Por exemplo, para$\small g(n) = \mathcal{O}(n^2)$ e $\small f(n) = \mathcal{O}(n^2)$, não é correto dizer $\small \frac{g(n)}{f(n)} = \mathcal{O}(1)$ (considerar $\small g(n) = n^2$ e $\small f(n) = n$) No entanto, se$c$ é uma constante fixa, então $\small \frac{g(n)}{c} = \mathcal{O}(n^2)$.

Para responder a perguntas como a sua conjectura, use a definição de $O$. Parafraseando da wikipedia no momento da escrita:

$f \in O(g)$ iff $f(x) \leq M\times g(x)$ para todos $x > x_0$, para algumas constantes $M$ e $x_0$.

Então se $f(n) \in O(2n^2)$, então $f(n) \leq C \times 2n^2 \ \ \forall n > n_0$ para algumas constantes $C$ e $n_0$ (Estou chamando $C$ ao invés de $M$para evitar confusão depois). Você notará que podemos combinar o$2C$ em uma constante, o que lhe diz $O(2n^2) = O(n^2)$.

O que podemos dizer sobre $f(n)/2$? Agora podemos usar álgebra normal na desigualdade, como dividir os dois lados por 2 para obter:

$f(n)/2 \leq Cn^2 \ \ \forall n > n_0$

Isso ainda $O(n^2)$? To check this, we need to find constants $M$ and $x_0$ such that the definition above holds. In this case, $M = C$ and $x_0 = n_0$ works. Notice that $M = 327.6C$ is also valid; you can use whatever method you want to find these constants, as long as you know they are constant.

In the real world you'll be able to "shortcut" most of this when doing your analysis, as NP-hard does in his answer, but those are just shortcuts for writing it out rigorously like this (which is what I would expect on homework specifically about $O$). If you're not sure whether it's valid, get the $O$s out by using the definition, perform algebra on the inequality, then get it back into $O$ by finding the appropriate constants (or simply showing that they do exist).