A community for students.
Here's the question you clicked on:
 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/electricalengineeringandcomputerscience/6046jintroductiontoalgorithmssma5503fall2005/videolectures/lecture2asymptoticnotationrecurrencessubstitutionmastermethod/
> around minute 3.
My calc background is extremely shaky, and I really don't understand what's going on there.
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/electricalengineeringandcomputerscience/6046jintroductiontoalgorithmssma5503fall2005/videolectures/lecture2asymptoticnotationrecurrencessubstitutionmastermethod/ > around minute 3. My calc background is extremely shaky, and I really don't understand what's going on there.

This Question is Closed

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0Specifically, it looks to me like that should be O(n^2) I thought that's what dropping the leading terms means.

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0hmm. Then the professor must've made a mistake. Thanks!

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0Recall that big 0 is an upper bound

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0So technically everything that's O(n) is also O(n^2) and all higher values?

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0Yeah, but we'd like to have as tight a bounds as possible

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0I'm watching the vid to see if I can figure out why he was using that

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0yeah he just made a mistake.

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0yeah, 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.

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0Because the definition is: \[f\in O(g(x)) \iff \exists C,k \text{ such that }f(x) \le Cg(x), \forall x >k \]

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0In this case \(f(x) = 2n^2, g(x) = n^2\) And my C would be 2 and my k would be 0

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0Actually any x value can serve as the k witness.

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0Ack. that's terrible notation, sorry.

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0Should be f(n) and g(n) not f(x) etc.
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.