patternMinor
Can you operate on and draw conclusions on functions described asymptotically?
Viewed 0 times
canyouconclusionsdrawasymptoticallyoperatedescribedandfunctions
Problem
This question is homework based (not using actual problem though)!
Say you have a function described as:
$$f(n) \in O(2n^2) \, .$$
Can you then go on the treat this as:
$$f(n) = 2n^2$$
and performs mathematics on it and keep its asymptotic meaning?
In the above case could I conjecture that $f(n) \in O(2n^2)$ implies $f(n) / 2 \in O(n^2)$ (assuming coefficients matter in this example)?
Say you have a function described as:
$$f(n) \in O(2n^2) \, .$$
Can you then go on the treat this as:
$$f(n) = 2n^2$$
and performs mathematics on it and keep its asymptotic meaning?
In the above case could I conjecture that $f(n) \in O(2n^2)$ implies $f(n) / 2 \in O(n^2)$ (assuming coefficients matter in this example)?
Solution
For some operations, such as addition, multiplication, you can operate directly on the asymptotic notation. For example, if $\small g(n) = \mathcal{O}(n^2)$ and $\small f(n) = \mathcal{O}(n^2)$, then $\small g(n) + f(n) = \mathcal{O}(n^2)$ and $\small g(n) \cdot f(n) = \mathcal{O}(n^4)$. For some other operations, such as division, it depends then. For example, for $\small g(n) = \mathcal{O}(n^2)$ and $\small f(n) = \mathcal{O}(n^2)$, it is not correct to say $\small \frac{g(n)}{f(n)} = \mathcal{O}(1)$ (consider $\small g(n) = n^2$ and $\small f(n) = n$). However, if $c$ is a fixed constant, then $\small \frac{g(n)}{c} = \mathcal{O}(n^2)$.
Context
StackExchange Computer Science Q#63909, answer score: 8
Revisions (0)
No revisions yet.