anonymous
  • anonymous
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 around minute 3. My calc background is extremely shaky, and I really don't understand what's going on there.
Mathematics
katieb
  • katieb
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
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.

Get this expert

answer on brainly

SEE EXPERT ANSWER

Get your free account and access expert answers to this
and thousands of other questions

anonymous
  • anonymous
Specifically, it looks to me like that should be O(n^2) --I thought that's what dropping the leading terms means.
anonymous
  • anonymous
It is O(n^2)
anonymous
  • anonymous
hmm. Then the professor must've made a mistake. Thanks!

Looking for something else?

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

More answers

anonymous
  • anonymous
Well
anonymous
  • anonymous
Recall that big 0 is an upper bound
anonymous
  • anonymous
So technically everything that's O(n) is also O(n^2) and all higher values?
anonymous
  • anonymous
Yeah, but we'd like to have as tight a bounds as possible
anonymous
  • anonymous
I'm watching the vid to see if I can figure out why he was using that
anonymous
  • anonymous
yeah he just made a mistake.
anonymous
  • anonymous
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.
anonymous
  • anonymous
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 \]
anonymous
  • anonymous
In this case \(f(x) = 2n^2, g(x) = n^2\) And my C would be 2 and my k would be 0
anonymous
  • anonymous
Actually any x value can serve as the k witness.
anonymous
  • anonymous
Ack. that's terrible notation, sorry.
anonymous
  • anonymous
Should be f(n) and g(n) not f(x) etc.
anonymous
  • anonymous
Cool. Thanks!

Looking for something else?

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