1
$\begingroup$

show whether $n2^n = 2^{O(n)}$ is true or not.

In my opinion, it's false because O(n) can be n and thus the equality will be wrong, because $n2^n$ grows much faster than $2^n$

$\endgroup$
  • 1
    $\begingroup$ But does it grow faster than $2^{1.00001n}$? $\endgroup$ – David Richerby Sep 22 '14 at 19:42
7
$\begingroup$

One way, if you want to prove that $n2^n \in 2^{\mathcal{O}(n)}$, is to show that there exists a $c \in \mathbb{R}$ such that $n2^n \le 2^{cn}$ for all $n$ greater than some $n_0 \in \mathbb{N}$.

Correspondingly, if you want to show the contrary, then you have to show that such a $c$ does not exist. However, we will see that the statement is true.

Choose $c = 2$, i.e., we ask whether $n2^n \le^? 2^{2n} = 4^n$ for all $n > n_0$. We know that $n \le 2^n$ for all $n \in \mathbb{N}$. Therefore, it also holds that $n2^n \le 2^n\cdot 2^n = 2^{2n}$. Hence, we have an upper bound for the function $n2^n$ by choosing $c = 2$. In this case, we can set $n_0 = 1$, for instance.

$\endgroup$
  • 2
    $\begingroup$ I'm not sure why you take $c=3$ when you've already observed ($n2^n\leq 2^{2n}$) that $c=2$ is enough. Obviously, $c=3$ works but it adds an unnecessary step to the proof. $\endgroup$ – David Richerby Sep 22 '14 at 20:33
4
$\begingroup$

The main issue here is to read that awful abuse of notation in the "right" way.

Let me translate:

Show whether $n2^n \in O(2^{f(n)})$ for some $f \in O(n)$.

That is, we understand

$\qquad\displaystyle 2^{O(g)} := \{ f \mid f \in O(2^{h(n)}), h \in O(g) \}$.

Note how, in particular, $c^n \in 2^{O(n)}$ with $f : n \mapsto n \cdot \log_2 c$ for all $c>1$.

The rest is mechanical.

$\endgroup$
  • 2
    $\begingroup$ "awful abuse of notation" +1 $\endgroup$ – Hendrik Jan Sep 22 '14 at 20:41
  • 2
    $\begingroup$ "awful abuse of notation" -1 (not really minus, but not plus either). It's not awful, it's very sensible, and makes things much more readable. $\endgroup$ – Pål GD Sep 22 '14 at 20:47
  • $\begingroup$ @PålGD I disagree. It's about 13 characters shorter for the price of being horrible to typeset and confusing half of the readership. (The "mistake" done by the OP is quite common.) Furthermore, it's overloaded; $2^X$ typically denotes the power set of $X$ (even though that would not make any sense in this here context.) For me, that's pretty much the definition of bad notation. But tastes differ, I guess. $\endgroup$ – Raphael Sep 22 '14 at 20:53
  • $\begingroup$ @Raphael Do you disagree with my disagreeing or with the notation being awful? On a more serious topic, it isn't the character count that counts for my part, but the readability. Having things in superscript isn't exactly an unsolved problem either, and if overloading is your main concern, then there are plenty of notation in mathematics to go mad over. In any case, I like it, and I will continue to use it. That's also the general consensus, it seems, for the community I'm in. $\endgroup$ – Pål GD Sep 22 '14 at 20:59
  • 4
    $\begingroup$ Nobody ever talks about the powerset of $\mathcal{O}(f(n))$ and, in any case, $\mathcal{P}(\cdot)$ is IME much more common. I'm pretty sure that nobody who is confused about what $2^{\mathcal{O}(f(n))}$ means is confused because they think it might be a powerset. $\endgroup$ – David Richerby Sep 22 '14 at 22:16

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.