How would I go about proving these.

Question

I need to prove or disprove these two problems, but I'm not sure I did it right. $$(a).\quad f(n) = 2^n+1 = O(2^n)\\ (b).\quad f(n) = 2^n+1 = Θ(2^n) .$$

What I tried for the first one is, $2^n+1/2^n \le C$ when $K>1$, and then get stuck.

I think I'm just having trouble proving BigO

$2^n+1$ or $2^{n+1}$. Before the edit it was like $2^{n+1}$. — Extremal, Mar 06 '15 at 23:51
Right right, I was actually just thinking that was why. Thanks. — John, Mar 06 '15 at 23:53

score 0 · Answer 1 · answered Mar 06 '15 at 23:44

0

$2^{n+1}\leq 3\times 2^n$ for all $n$. So, $2^{n+1}=O(2^n)$

answered Mar 06 '15 at 23:44

Extremal

5,785

That makes sense, is 3 the constant? – John Mar 06 '15 at 23:46
Yes. $C=3$ and $k=1$ – Extremal Mar 06 '15 at 23:47
And just so I understand how did you choose 3. – John Mar 06 '15 at 23:48

score 0 · Answer 2 · answered Mar 07 '15 at 00:05

0

$${2^{n}+1 \over 2^n}=1+{1\over{2^n}}\le 1+{1\over{2}}={3\over 2}$$ that is $$2^{n}+1\le {3\over 2}\times 2^n$$

answered Mar 07 '15 at 00:05

Fermat

5,230

How would I go about proving these.

2 Answers2