Show that 2^n+1 is 0(2^n)

- anonymous

Show that 2^n+1 is 0(2^n)

- Stacey Warren - Expert brainly.com

Hey! We 've verified this expert answer for you, click below to unlock the details :)

- schrodinger

I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!

- anonymous

are you sure of what you just whrite

- anonymous

That is the same question I asked the professor!

- anonymous

Is that expression multiplied by zero ? 0(2^n)

Looking for something else?

Not the answer you are looking for? Search for more explanations.

## More answers

- geerky42

No it's big O notation.

- geerky42

\(2^n+1 = O(2^n)\)

- geerky42

Right? @kattck

- anonymous

That is what I was thinking at first but how it is written I have asked and it does represent the number 0

- anonymous

Well, if it is, I haven't seen anything like this before. For me, that expression is equal to 0, there is no such 'n' for 2^2 + 1 to be zero.

- anonymous

sorry, I was going to write 2^n+1

- geerky42

Well, it's not what big O means.

- geerky42

What class are you in? @kattck

- anonymous

Yah this would be false statement correct?

- anonymous

yes

- anonymous

This is discrete Mathematic Comp Science

- geerky42

then I'm pretty sure it's big O.

- anonymous

What subjects did your proffessor explained you so far?

- geerky42

Do you have note about it? What is this "0"?

- geerky42

What is definition of 0( f(x) )?

- anonymous

I found a whole section on Big-"OH" notation!

- anonymous

geerky42 You were right!

- geerky42

Yeah :)
What is definition of big O, if you were given?

- geerky42

Then from here, we can figure out how to show etc

- geerky42

Or you can use this: https://www.cs.utexas.edu/users/tandy/big-oh.pdf

- anonymous

ok so big OH is measuerment time of the execution of the algorithm

- geerky42

Well, yeah that's what big O is often used for.

- geerky42

In your question, by "show," you mean like prove?

- anonymous

Yah this section is mostly about proving the algorithms.

- geerky42

OK, so from definition in link, \(2^n+1 = O(2^n)\) if there exist positive constant \(C_1\) and \(C_2\) such that \(2^n+1\le C_1~ 2^n\) for all \(n>C_2\)|dw:1433116401018:dw|
You get the idea, right?

- geerky42

Proving is pretty easy; all we need to do is finding value of \(C_1\) and \(C_2\).

- geerky42

My bad, actually there is more than that...

- geerky42

for this case, we can let \(C_1 = 2\)
Then we have \(2^n+1 \le 2(2^n) = 2^{n+1}\)
Now we need to know value of \(C_2\)
at \(n = 0\), we have \(2\le 1\); FALSE
at \(n = 1\), we have \(3\le 4\)
So we can have \(C_2 = 1\)
Now we just need to show that \(2^n+1 \le 2^{n+1}\) for all \(n>1\)
Any idea?

- geerky42

Maybe proof by induction? I'm not very familiar with proof though.

- anonymous

what is the le?

- geerky42

Do you understand what I'm saying so far>

- geerky42

le?

- anonymous

\(3\le <-- 4\)

- geerky42

It's less than or equal to. ?

- anonymous

ok ok that makes sense! Awsome man you have been a great help!

- anonymous

man/woman

- geerky42

ok, so you know how to prove it?

- geerky42

Glad I helped.

- anonymous

Yes! took me sometime but I got it thank you!

- geerky42

ok great! Good luck.

Looking for something else?

Not the answer you are looking for? Search for more explanations.