4
$\begingroup$

These are all from Sipser's book, second edition. I was just hoping someone could verify/explain those that are more difficult for me.

$2n = O(n)$: true

$n^2 = O(n)$: false

$n^2 = O(n\log^2 n)$: I say false, because $\log^2 n$ grows more slowly than $n$

$n\log n = O(n^2$): true because $n$ grows more quickly than $\log^2n$

$3^n = 2^{O(n)}$: I wasn't sure what this notation meant. Any clarification here?

$2^{2^n} = O(2^{2^n})$: I would say true, but I'm not entirely sure why.

$n = o(2n)$: false, because $o(2n) = o(n)$ and $n$ grows as quickly as itself.

$2n = o(n^2)$: true, $n^2$ is always more than $2n$ for some constant.

$2^n = o(3^n)$: true

$1 = o(n)$: I'm not really sure.

$n = o(\log n)$: false, $n$ is always larger.

$1 = o(1/n)$: true, because 1 is always larger.

$\endgroup$

2 Answers 2

1
$\begingroup$

I want to add to LAcarguy's answer to develop some intuition. When looking at exponentials of the form $a^{f(n)}$ vs. $b^{f(n)}$, $a^{f(n)} \in O(b^{f(n)})$ when $a \leq b$. Note that this assumes $f(n)$ is an increasing, positive function. In computational complexity, this is usually a fair assumption, but not always.

Little-o is a strict inequality, whereas Big-O is a weak-inequality. This means that if $f(n) = o(g(n))$, then we have a positive constant $C$ such that $|f(n)| < C * |g(n)|$ as $n$ tends to infinity.

Using this definition, we quickly see that $1 = \frac{1}{n}$ only when $n = 1$. A constant of $C$ may allow for $\frac{C}{n} \geq 1$ for more values of $n$, but we still will only have finite values of $n$ for when this happens. Eventually, we see the $n$ term dominate out the constant; and thus, $\frac{1}{n} = o(1)$. The limit test that LAcarguy mentioned describes the mathematics behind this intution.

For your question about $2^{2^{n}} = O(2^{2^{n}})$, you are correct. Look at the definition of Big-O to see why. We need constants $C, k \in \mathbb{R}^{+}$ such that $2^{2^{n}} \leq C * 2^{2^{n}}$, for all $n \geq k$. Let $C = k = 1$. We have now satisfied the definition of Big-O.

An alternative way to look at $2^{2^{n}} = O(2^{2^{n}})$ is with Big-Theta. Big-Theta is an equivalence relation that says $f(n) = \Theta(g(n))$ if and only if we have a constant $C$ such that $|f(n)| = C * |g(n)|$ as $n$ tends to infinity. Setting $C = 1$ gives us equivalence of $f(n)$ to itself. This is the reflexive property of Big-Theta being an equivalence relation. Big-Theta has a couple of other equivalent definitions. $f(n) = \Theta(g(n))$ if and only if $f(n) = O(g(n))$ and $g(n) = O(f(n))$. Equivocally, $f(n) = O(g(n)) \leftrightarrow g(n) = \Omega(f(n))$. If you haven't learned about Big-Theta and this is confusing, feel free to ignore it. If it helps you with the intuition, by all means, use it.

Hopefully this helps clarify things, though!

$\endgroup$
7
  • $\begingroup$ It is possible for you to elaborate on the $3^n = 2^{O(n)}$ question? I'm still not exactly sure what this is saying. $\endgroup$ Mar 20, 2014 at 6:14
  • $\begingroup$ In this context, $O(n)$ means we can take $2^{f(n)}$ where $f(n) = O(n)$. $2^{log_{2}(n)}$ is acceptable, as is $2^{kn}$, for a constant $k$. The question here really is: is $3^{n}$ bounded above by $2^{f(n)}$, for any function $f(n) = O(n)$? The answer here is yes. We get it by taking an obvious worst case- $n$ (or $kn$ for some $k > 1$). Then you can apply the limit test as LAcarguy showed you. $lim_{n \to \infty} \frac{3^{n}}{2^{n}} = \infty$, which implies that $2^{O(n)} = o(3^{n})$. So by definition, $2^{O(n)} = O(3^{n})$. $\endgroup$
    – ml0105
    Mar 20, 2014 at 6:18
  • $\begingroup$ How does this show that $3^n = 2^{O(n)}$ is false, though? $\endgroup$ Mar 20, 2014 at 6:20
  • $\begingroup$ It shows $2^{O(n)} = o(3^{n})$. As little-o is a strict inequality, we can't have $3^{n} = O(2^{O(n)})$. Let $L = \lim_{n \to \infty} \frac{f(n)}{g(n)}$. If $L = \infty$, $g(n) = o(f(n))$. If $0 < L < \infty$, then $f(n) = \Theta(g(n))$. Otherwise, $f(n) = o(g(n))$. $\endgroup$
    – ml0105
    Mar 20, 2014 at 6:22
  • 1
    $\begingroup$ I found this reference here: cs.stackexchange.com/questions/7091/why-is-3n-2on-true Does your definition suggest otherwise? $\endgroup$ Mar 20, 2014 at 6:24
0
$\begingroup$

3^n = 2^(O(n)) is false: Look at n = O(n) and 3^n/2^n = 1.5^n --> + infinity as n --> infinity. So it is false.

1 = o(n) is true because 1/n --> 0 as n --> infinity.

1 = o(1/n) is false because 1/(1/n) = n --> infinity as n --> infinity, but it is supposed to go to zero.

$\endgroup$
1
  • 1
    $\begingroup$ "3^n = 2^(O(n)) is false" Well, actually it is not (false). $\endgroup$
    – Did
    Mar 20, 2014 at 6:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .