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
  • Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
SOLVED
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.
jamiebookeater
  • jamiebookeater
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
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.