3

To show that $2^n$ is $\mathcal{O}(3^n)$ is straightforward. On the other hand, if we want to show the opposite that $3^n$ were $\mathcal{O}(2^n)$, then we would have $3^n\le C·2^n$ for all sufficiently large $n$. This is equivalent to $C\ge (\frac{3}{2})^n$, which is clearly impossible, since $(\frac{3}{2})^n$ grows without bound as $n$ increases.

Question:is it clearly impossible based on the question because $C$ is supposed to be constant in the definition of Big-$\mathcal{O}$?

Avv
  • 1,159

1 Answers1

3

This is too long for a comment, but worth pointing out. Rosen's approach for analyzing asymptotics is nice, because it doesn't rely on Calculus techniques. So in that sense, it is more accessible. On the other hand, the Calculus techniques are quite nice for showing things like $f(n) \not \in \mathcal{O}(g(n))$.

Fix $k \geq 0$, and suppose that $f, g : \mathbb{Z}_{\geq k} \to \mathbb{R}$ satisfy that the following limit exists: \begin{align} L := \lim_{n \to \infty} \left| \frac{f(n)}{g(n)} \right|. \end{align}

We have the following:

  • If $L = 0$, then $f(n) \in o(g(n))$. That is, $f(n) \in \mathcal{O}(g(n))$ and $f(n) \neq \Theta(g(n))$. Put another way, $f(n) \in \mathcal{O}(g(n))$ and $g(n) \not \in \mathcal{O}(f(n))$.
  • If $0 < L < \infty$, then $f(n) = \Theta(g(n))$. Put another way, $f(n) \in \mathcal{O}(g(n))$ and $g(n) \in \mathcal{O}(f(n))$.
  • If $L = \infty$, then $f(n) \in \omega(g(n))$. That is, $f(n) \not \in \mathcal{O}(g(n))$, but $g(n) \in \mathcal{O}(f(n))$.

Computing limits is sometimes much easier than trudging through these tedious inequalities.

ml0105
  • 14,674