Menu
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?
706
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). That inequality holding true is enough to prove that f(n) is O(n^3).
the Big-Oh condition holds for n ≥ n0 = 1 and c ≥ 22 (= 1 + 20 + 1). Larger values of n0 result in smaller factors c (e.g., for n0 = 10 c ≥ 1.201 and so on) but in any case the above statement is valid.
C is probably popular simply because it's the first letter of "constant". At most, it's a convention. You could use some other letter and the meaning would be the same.
the value n0 is some cutoff threshold. That is, it's the point where we say that n is "sufficiently large."
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.)
92
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
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
