# Big O proofs

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

## 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 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...)

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 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 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 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 on other sites

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

This topic is now closed to further replies.

1. 1
2. 2
Rutin
20
3. 3
khawk
16
4. 4
A4L
14
5. 5

• 11
• 16
• 26
• 10
• 11
• ### Forum Statistics

• Total Topics
633756
• Total Posts
3013707
×