Big-O notation finding c and n0

Question

I've just been introduced to Big-O notation and I've been given some questions. However I'm confused as to how to determine the value of n0. I have to show that 3n^3 +20n^2 + 5 is O(n^3). So far I have:

3n^3 + 20n^2 + 5 <= cn^3

(3 - c)n^3 + 20n^2 + 5 <= 0

5 <= n^3(c - 3) - 20n^2

5 <= n^2(n(c - 3) - 20)

I just don't know what to do from here to find n0 and c. Would someone mind explaining?

Answer 1

Divide by n^3 we get 3+20/n+5/n^3<=C 20/n+5/n^3<=C-3

Take C value as 10 20/n+5/n^3<=7

We need to solve this for different values of n until the condition gets satisfied C=10 and n0 = 3 will give the solution

Answer 2

If you have f(n) = (3n^3 + 20n^2 + 5) and you want to see if it's O(g(n)) where g(n) = n^3, I believe you can take the limit of f(n)/g(n) as n->infinity.

Because the limit is 3, you can see that 3n^3 + 20n^2 + 5 only grows as fast as n^3. When you have a polynomial like 3n^3 + 20n^2 + 5, you can tell by inspection that the largest order term will always be the value of O(f(n)).

It's not a lot of help finding n₀ and C, but it's a relatively easy way to determine what the order of something is. As the others have said here, you can just pick n₀ and then calculate C.

If you choose n₀ = 1, then you have 3*(1^3) + 20*1^2 + 5 = 28. So if c1^3 <= 28, c must be 28. You've shown there there is a c and n0 that meets this condition, so you've proved f(n) is O(n^3)

Answer 3

3n^3 + 20n^2 + 5 <= cn^3
=> 20n^2 + 5 <= cn^3 - 3n^3
=> 20n^2 + 5 <= n^3(c - 3)
=> 20n^2/n^3 + 5/n^3 <= n^3(c - 3)/n^3
=> 20/n + 5/n^3 <= c - 3
=> c >= 20/n + 5/n^3 + 3

Depending on where you want the greater than condition to begin, you can now choose n0 and find the value.

For example, for n0 = 1:

c >= 20/1 + 5/1 + 3 which yields c >= 28

It's worth noting that by the definition of Big-O notation, it's not required that the bound actually be this tight. Since this is a simple function, you could just guess-and-check it (for example, pick 100 for c and note that the condition is indeed true asymptotically).

For example:

3n^3 + 20n^2 + 5 <= (5 * 10^40) * n^3 for all n >= 1

That inequality holding true is enough to prove that f(n) is O(n^3).

---

To offer a better proof, it actually needs to be shown that two constants, c and n0 exist such that f(n) <= cg(n) for all n > n0.

Using our c = 28, this is very easy to do:

3n^3 + 20n^2 + 5 <= 28n^3
20n^2 + 5 <= 28n^3 - 3n^3
20n^2 + 5 <= 25n^3
20/n + 5/n^3 <= 25

When n = 1: 20 + 5 <= 25 or 25 <= 25
For any n > 1, 20/n + 5/n^3 < 25, thus for all n > 1 this holds true.

Thus 3n^3 + 20n^2 + 5 <= 28n^3 is true for all n >= 1

(That's a pretty badly done 'proof' but hopefully the idea shows.)

Answer 4

3n^3 + 20n^2 + 5 <= cn^3

5 + 20n^2 <= n^3(c - 3)

5/n^3 + 20/n <= c - 3

For n0 = 20, c >= 5, since 5/n^3 + 20/n < 2