1
$\begingroup$

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

migrated from stackoverflow.com Feb 17 '17 at 7:33

This question came from our site for professional and enthusiast programmers.

1
$\begingroup$

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.

$\endgroup$
  • $\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$ – David Richerby Feb 17 '17 at 9:16
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy