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$
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ But does it grow faster than $2^{1.00001n}$? $\endgroup$– David RicherbyCommented Sep 22, 2014 at 19:42
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
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.
-
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$ Commented Sep 22, 2014 at 20:33
$\begingroup$
$\endgroup$
6
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.
-
2$\begingroup$ "awful abuse of notation" +1 $\endgroup$ Commented Sep 22, 2014 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$ Commented Sep 22, 2014 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$– RaphaelCommented Sep 22, 2014 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$ Commented Sep 22, 2014 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$ Commented Sep 22, 2014 at 22:16