Tuesday, 11 November 2014

Big-Oh of polynomials

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