A community for students.
Here's the question you clicked on:
 0 viewing
anonymous
 one year ago
Show that 2^n+1 is 0(2^n)
anonymous
 one year ago
Show that 2^n+1 is 0(2^n)

This Question is Open

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0are you sure of what you just whrite

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0That is the same question I asked the professor!

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0Is that expression multiplied by zero ? 0(2^n)

geerky42
 one year ago
Best ResponseYou've already chosen the best response.2No it's big O notation.

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0That is what I was thinking at first but how it is written I have asked and it does represent the number 0

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0Well, 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
 one year ago
Best ResponseYou've already chosen the best response.0sorry, I was going to write 2^n+1

geerky42
 one year ago
Best ResponseYou've already chosen the best response.2Well, it's not what big O means.

geerky42
 one year ago
Best ResponseYou've already chosen the best response.2What class are you in? @kattck

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0Yah this would be false statement correct?

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0This is discrete Mathematic Comp Science

geerky42
 one year ago
Best ResponseYou've already chosen the best response.2then I'm pretty sure it's big O.

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0What subjects did your proffessor explained you so far?

geerky42
 one year ago
Best ResponseYou've already chosen the best response.2Do you have note about it? What is this "0"?

geerky42
 one year ago
Best ResponseYou've already chosen the best response.2What is definition of 0( f(x) )?

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0I found a whole section on Big"OH" notation!

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0geerky42 You were right!

geerky42
 one year ago
Best ResponseYou've already chosen the best response.2Yeah :) What is definition of big O, if you were given?

geerky42
 one year ago
Best ResponseYou've already chosen the best response.2Then from here, we can figure out how to show etc

geerky42
 one year ago
Best ResponseYou've already chosen the best response.2Or you can use this: https://www.cs.utexas.edu/users/tandy/bigoh.pdf

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0ok so big OH is measuerment time of the execution of the algorithm

geerky42
 one year ago
Best ResponseYou've already chosen the best response.2Well, yeah that's what big O is often used for.

geerky42
 one year ago
Best ResponseYou've already chosen the best response.2In your question, by "show," you mean like prove?

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0Yah this section is mostly about proving the algorithms.

geerky42
 one year ago
Best ResponseYou've already chosen the best response.2OK, 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
 one year ago
Best ResponseYou've already chosen the best response.2Proving is pretty easy; all we need to do is finding value of \(C_1\) and \(C_2\).

geerky42
 one year ago
Best ResponseYou've already chosen the best response.2My bad, actually there is more than that...

geerky42
 one year ago
Best ResponseYou've already chosen the best response.2for 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
 one year ago
Best ResponseYou've already chosen the best response.2Maybe proof by induction? I'm not very familiar with proof though.

geerky42
 one year ago
Best ResponseYou've already chosen the best response.2Do you understand what I'm saying so far>

geerky42
 one year ago
Best ResponseYou've already chosen the best response.2It's less than or equal to. ?

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0ok ok that makes sense! Awsome man you have been a great help!

geerky42
 one year ago
Best ResponseYou've already chosen the best response.2ok, so you know how to prove it?

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0Yes! took me sometime but I got it thank you!
Ask your own question
Sign UpFind more explanations on OpenStudy
Your question is ready. Sign up for free to start getting answers.
spraguer
(Moderator)
5
→ View Detailed Profile
is replying to Can someone tell me what button the professor is hitting...
23
 Teamwork 19 Teammate
 Problem Solving 19 Hero
 Engagement 19 Mad Hatter
 You have blocked this person.
 ✔ You're a fan Checking fan status...
Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.