Operations on asymptotic notations

Question

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)$?

Answer 1

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.

Answer 2

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.