A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

anonymous

  • 5 years ago

Why is 2n^2 = O(n^3) ? This is given as an example of big O notation in the MIT OCW Introduction to Algorithms (SMA 5503) course. It's in lecture 2 < http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-2-asymptotic-notation-recurrences-substitution-master-method/ > around minute 3. My calc background is extremely shaky, and I really don't understand what's going on there.

  • This Question is Closed
  1. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Specifically, it looks to me like that should be O(n^2) --I thought that's what dropping the leading terms means.

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

    It is O(n^2)

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

    hmm. Then the professor must've made a mistake. Thanks!

  4. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Well

  5. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Recall that big 0 is an upper bound

  6. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    So technically everything that's O(n) is also O(n^2) and all higher values?

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

    Yeah, but we'd like to have as tight a bounds as possible

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

    I'm watching the vid to see if I can figure out why he was using that

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

    yeah he just made a mistake.

  10. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    yeah, I was really confused. It seems like the point of big O notation is to try to describe the growth of functions for arbitrarily large inputs, but calling that O(n^3) only seems to describe the function's behavior for n = 2.

  11. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Because the definition is: \[f\in O(g(x)) \iff \exists C,k \text{ such that }|f(x)| \le C|g(x)|, \forall x >k \]

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

    In this case \(f(x) = 2n^2, g(x) = n^2\) And my C would be 2 and my k would be 0

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

    Actually any x value can serve as the k witness.

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

    Ack. that's terrible notation, sorry.

  15. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Should be f(n) and g(n) not f(x) etc.

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

    Cool. Thanks!

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