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

2 Answers 2


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.

  • $\begingroup$ 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. $\endgroup$ Commented Feb 17, 2017 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.