A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

anonymous

  • one year ago

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

  • This Question is Open
  1. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    are you sure of what you just whrite

  2. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    That is the same question I asked the professor!

  3. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  4. geerky42
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    No it's big O notation.

  5. geerky42
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  6. geerky42
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    Right? @kattck

  7. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  8. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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.

  9. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  10. geerky42
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    Well, it's not what big O means.

  11. geerky42
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    What class are you in? @kattck

  12. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Yah this would be false statement correct?

  13. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    yes

  14. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    This is discrete Mathematic Comp Science

  15. geerky42
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  16. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    What subjects did your proffessor explained you so far?

  17. geerky42
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  18. geerky42
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  19. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  20. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    geerky42 You were right!

  21. geerky42
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  22. geerky42
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  23. geerky42
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  24. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  25. geerky42
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  26. geerky42
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  27. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Yah this section is mostly about proving the algorithms.

  28. geerky42
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    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?

  29. geerky42
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  30. geerky42
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  31. geerky42
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    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?

  32. geerky42
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  33. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    what is the le?

  34. geerky42
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    Do you understand what I'm saying so far>

  35. geerky42
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    le?

  36. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    \(3\le <-- 4\)

  37. geerky42
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    It's less than or equal to. ?

  38. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  39. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    man/woman

  40. geerky42
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    ok, so you know how to prove it?

  41. geerky42
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    Glad I helped.

  42. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  43. geerky42
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    ok great! Good luck.

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

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy

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
  • 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.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.