anonymous
  • anonymous
Show that 2^n+1 is 0(2^n)
Discrete Math
  • Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
SOLVED
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
jamiebookeater
  • jamiebookeater
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
anonymous
  • anonymous
are you sure of what you just whrite
anonymous
  • anonymous
That is the same question I asked the professor!
anonymous
  • 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
  • geerky42
No it's big O notation.
geerky42
  • geerky42
\(2^n+1 = O(2^n)\)
geerky42
  • geerky42
Right? @kattck
anonymous
  • 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
  • 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
  • anonymous
sorry, I was going to write 2^n+1
geerky42
  • geerky42
Well, it's not what big O means.
geerky42
  • geerky42
What class are you in? @kattck
anonymous
  • anonymous
Yah this would be false statement correct?
anonymous
  • anonymous
yes
anonymous
  • anonymous
This is discrete Mathematic Comp Science
geerky42
  • geerky42
then I'm pretty sure it's big O.
anonymous
  • anonymous
What subjects did your proffessor explained you so far?
geerky42
  • geerky42
Do you have note about it? What is this "0"?
geerky42
  • geerky42
What is definition of 0( f(x) )?
anonymous
  • anonymous
I found a whole section on Big-"OH" notation!
anonymous
  • anonymous
geerky42 You were right!
geerky42
  • geerky42
Yeah :) What is definition of big O, if you were given?
geerky42
  • geerky42
Then from here, we can figure out how to show etc
geerky42
  • geerky42
Or you can use this: https://www.cs.utexas.edu/users/tandy/big-oh.pdf
anonymous
  • anonymous
ok so big OH is measuerment time of the execution of the algorithm
geerky42
  • geerky42
Well, yeah that's what big O is often used for.
geerky42
  • geerky42
In your question, by "show," you mean like prove?
anonymous
  • anonymous
Yah this section is mostly about proving the algorithms.
geerky42
  • 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
  • geerky42
Proving is pretty easy; all we need to do is finding value of \(C_1\) and \(C_2\).
geerky42
  • geerky42
My bad, actually there is more than that...
geerky42
  • 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
  • geerky42
Maybe proof by induction? I'm not very familiar with proof though.
anonymous
  • anonymous
what is the le?
geerky42
  • geerky42
Do you understand what I'm saying so far>
geerky42
  • geerky42
le?
anonymous
  • anonymous
\(3\le <-- 4\)
geerky42
  • geerky42
It's less than or equal to. ?
anonymous
  • anonymous
ok ok that makes sense! Awsome man you have been a great help!
anonymous
  • anonymous
man/woman
geerky42
  • geerky42
ok, so you know how to prove it?
geerky42
  • geerky42
Glad I helped.
anonymous
  • anonymous
Yes! took me sometime but I got it thank you!
geerky42
  • geerky42
ok great! Good luck.

Looking for something else?

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