Jump to content
  • Advertisement
Sign in to follow this  
embryo_9

Big O proofs

This topic is 5039 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm trying to prove that 3n^3 - 2n^2 + 5nlog(n) + 10 is O(n^3). So I said that 3n^3 - 2n^2 + 5nlog(n) + 10 <= 3n^3 + 5n^3 + 10n^3 for all n >= 1. However, I'm not sure if I can just make the claim that 5n^3 is >= 5nlog(n) without proving it. Can somebody help with this. If I try to prove it using induction I get stuck on the induction step because I'm not sure how to make 3k^3 > klog(k) imply that 3(k+1)^3 > (k+1)log(k+1). Also I have to prove that 3n^3 - 2n^2 + 5nlog(n) + 10 is not O(n^2). To do this I have to come up with an n such that for any positive real number c and any natural number B. n >= B and 3n^3 - 2n^2 + 5nlog(n) + 10 > cn^2. But n has to depend on c and B. Somebody said to solve for n to get something with c and B in it but I'm not sure how to do that with the nlog(n) in there. I hope somebody can help because this is driving me crazy.

Share this post


Link to post
Share on other sites
Advertisement
Here's what I have:

5n^3 > 5nlog(n)
n^3 > nlog(n)
n^2 > log(n)
if n > 1:
n > log(n)

when n is 1, the inequality is:
n > log(n) => 1 > 0
which is true

dx[x] = 1
dx[log(x)] = 1/(ln(10) x)

1 > 1/(ln(10) x) for all x > 1
therefor, n > log(n) will always be true (I know this because it is true at n = 1 and the left side always increases faster than the right. I could use an integral to write this formally...)

hopefully that made some sence.

About the second half. the inequality: 3n^3 - 2n^2 + 5nlog(n) + 10 > cn^2 is not always true. I set n = 2 and c = 10 Then inequality becomes 29.8229 > 41.0191. I must have misunderstood what you were trying to proove.

Share this post


Link to post
Share on other sites
I'm assuming this is a HW question, which they don't like around here, but I'll answer anyway.

3n^3 - 2n^2 + 5nlog(n) + 10 is O(n^3)

First you can scrap all the constants, since it's irrelevent to asymptotic behaviour.

3n^3 - 2n^2 + 5nlog(n) + 10 is O(n^3)
=
n^3 - n^2 + nlog(n) is O(n^3)

You can also ignore lesser terms, for the same reason above. The n^2 is definitely less than n^3, and so is the nlogn, considering that logn < n.

That leaves you with n^3.

Share this post


Link to post
Share on other sites
Dwiel: Thanks for the bit about n > log(n) for n > 1. That helped quite a bit.
As for the second part, c cannot be chosen, it has to work for any c. I think I have an idea where to go with that though.

outRider: Thanks for the help but it has to be a more formal proof than simply ignoring constants and lower terms. It's ok though, I think I have it figured out.

Share this post


Link to post
Share on other sites
I'm closing the thread, since it does sound an awful lot like schoolwork and since the poster did not follow the Forum FAQ rules for this type of post (e.g., did not show all of his work first). Review the Forum FAQ for the complete forum guidelines on schoolwork or schoolwork-like problems.

Share this post


Link to post
Share on other sites

This topic is 5039 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Guest
This topic is now closed to further replies.
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!