Sign in to follow this  

Big O proofs

This topic is 4756 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
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

This topic is 4756 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