Definition of O(n2)
Basically, f(n) is in O(n2) iff ∃c∈R+, ∃B∈N, such that ∀n∈N, n≥B ⇒ f(n)≤cn2
In english, the statement is saying that there exists a number i that is greater than B (breakpoint) such that f(n) is upper bounded by cn2.
Now when proving a polynomial is upper bounded by O(n2), it is all about picking c and B.
- The first thing is to pick a c which should be larger than than the constant factor of the highest-order term in the polynomial.
- Next is to pick a B, usually B = 1 works in most cases but should be careful when doing so.
For an example, 7n6-5n4+2n3 ∈ O(6n8-4n5+n2)
Some things to consider or make assumption is to:
1) assume n ≥ 1
2)Upper bound the left side by overestimating
2)Lower bound the right side by underestimating
3)Finally, choose a c that connects the two bounds.
7n6-5n4+2n3 ∈ O(6n8-4n5+n2)
pick c = 9/2
pick B = 1
assume n∈N
assume n≥1
then 7n6-5n4+2n3 ≤ 7n6+2n3
#-5n4 ≤ 0
≤
7n6+2n6 = 9n6 #n3 ≤ n6since n ≥ 1
= (9/2)2n6 = c2n6
# c = 9/2
≤ c2n8 = c(6n8 - 4n8) ≤ c(6n8 - 4n5)
# -n8 ≤ -n5
≤ c(6n8-4n5+n2)
# 0 ≤ n2
then 7n6-5n4+2n3 ≤ c(6n8-4n5+n2)
<introduce the antecedent and quantifiers and you are done!>
I think the biggest advice before tackling such proofs is to first set 6n8-4n5+n2 as the largest(which the polynomial be upper bounded to) and set the 7n6-5n4+2n3 (the polynomial to be bounded by O(n2)) to be the lowest. Afterwards you slowly decrease the upper bound and increase the lowest and meet halfway by choosing a c that connects the two bounds.
No comments:
Post a Comment