# Operations on asymptotic notations

How to use algebra in operations that involve asymptotic notation? Like for example:

• $C_1(n)= O(n)$
• $C_2(n) = O(n^2)$
• Is $C_2(n)/C_1(n) = O(n)$?

## Yes and no.

A function $f(n)$ is said to be $O(g(n))$ if there exists a constant $c$ such that

$$\lim_{n\rightarrow \infty}\dfrac{f(n)}{g(n)} \leq c$$

Knowing this, a few things immediately become apparent:

• Addition and subtraction preserves the largest $O$ of the result, thanks to the properties of limits.

For instance, $f(n) \pm h(n)$ are $O(g(n))$ if both $f$ and $h$ are individually $O(g(n))$.

This is why you can say, if two operations are $O(n)$, then the resulting sum/subtraction is also $O(n)$.

If either $f$ or $h$ were $O(n^{2})$, then the result would be $O(n^{2})$. This is in agreement with intuition.

• A function that is $O(n)$ is also $O(n^{2}), O(n^{3})$, etc. as you can prove by this definition.

For practical purposes, that is immaterial, as you only usually care about the smallest upper bound.

• Multiplication can be simplified in the manner you require.

For instance, say I have $f, h$ that are both $O(n)$. This means

$$\lim_{n \rightarrow \infty}\dfrac{f(n)}{n} < c\;\;\mathrm{and} \; \; \lim_{n \rightarrow \infty}\dfrac{h(n)}{n} < c$$

or, equivalently,

$$\lim_{n \rightarrow \infty} f(n) < \lim_{n\rightarrow \infty} cn\;\;\mathrm{and} \; \; \lim_{n \rightarrow \infty}h(n) < \lim_{n\rightarrow \infty} cn$$

I can then argue that $f \times h$ is $O(n^{2})$, since, when we go to calculate it, this would require:

$$\lim_{n\rightarrow \infty}\dfrac{f \times h}{n^{2}} < c$$

which we can prove like so by substituting the inequalities above:

$$\lim_{n\rightarrow \infty}\dfrac{f \times h}{n^{2}} < \lim_{n\rightarrow \infty} \dfrac{cn \times cn}{n^{2}} < c^{2}\;\;\mathrm{which\;is\;a\;constant!}$$

In general, the product of two polynomial operations of order $O(n^{k}), O(n^{p})$ is at least $O(n^{k+p})$.

• Division is a bit trickier. Let's take your example: say we have $f, h$ both $O(n)$.

We now try to calculate the limit, using the properties formally stated above, and find:

$$\lim_{n \rightarrow \infty}\dfrac{\frac{f}{h}}{n} < \lim_{n \rightarrow \infty} \dfrac{\frac{cn}{cn}}{n} < lim_{n \rightarrow \infty} \dfrac{1}{n} = 0 < c$$

so it is $O(n)$.

But wait a minute! It is also $O(1)$:

$$\lim_{n \rightarrow \infty}\dfrac{\frac{f}{h}}{1} < \lim_{n \rightarrow \infty} \dfrac{\frac{cn}{cn}}{1} < lim_{n \rightarrow \infty} \dfrac{1}{1} = 1 < c$$

so the same operation is somehow both $O(1)$ and $O(n)$ at the same time.

No, this is not some quantum spookiness at work. Remember that a function that is $O(n^{c})$ is also $O(n^{k})$ if $k > c$, as we stated above. Correctly speaking, it is not wrong to say either $O(1)$ or $O(n)$ or any other higher power (excluding deities).

In such cases, you may want to use the much stronger $\theta$ definition, which says a function $f$ is $\theta(g(n))$ if $f(n)$ is $O(g(n))$ and $g(n)$ is $O(f(n))$ i.e. they grow at the same pace.

• Your section about division is wrong. In particular, knowing that $\lim f, \lim h<cn$ does not mean that $\lim(f/h)<cn/cn=1$. For example, consider $f(n)=n$ and $g(n)=1/n$. We have $f,g=O(n)$ but $f/g=n^2\notin O(n)$. To be able to upper-bound $f/g$, you would need an upper bound for $f$ and a lower bound for $g$, but $O(\cdot)$ only gives you the upper bound. – David Richerby Feb 17 '17 at 9:16

You cannot divide asymptotic notations in this way, since big O is only an upper bound. For example, if you take $C_1(n) = 1$ and $C_2(n) = n^2$ then $C_2(n)/C_1(n)$ is not $O(n)$.

If you're confused, think instead of the following question:

• Given $C_1(n) \leq n$ and $C_2(n) \leq n^2$, does $C_2(n)/C_1(n) \leq n$ necessarily hold?

Big O is very similar to $\leq$, the main difference being that we ignore multiplicative constants.