HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Can you operate on and draw conclusions on functions described asymptotically?

Submitted by: @import:stackexchange-cs··
0
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)?

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.