Reflection of CSC165 Lec.9 Nov. 5th

9.1  Big O proof

Def of O(n2)

A function f(n) is in O(n2) iff:

∃c∈R+, ∃B∈N, such that ∀ n∈N, n ≥B → f(n) ≤ cn2

In English, it means beyond the breakpoint B, f(n) is upper-bounded by cn2, where c is some wisely chosen constant multiplier.

Now let's try to prove 3n2 + 2n ∈ O(n2)

Which means it should fits:

∃c∈R+, ∃B∈N, such that ∀ n∈N, n ≥B → f(n) ≤ cn2

f(n) =  3n2 + 2n, in order to let  f(n) ≤ cn2, c should be larger than 3

Moreover, 3n2 + 2n < 3n2 + 2n2 = 5n2

So, c could be 5 and b could be 1 as it satisfies the condition.

Proof: 3n2 + 2n ∈o(n2) 

3n2 + 2n: N→R>0

Pick c = 5, then c ∈R+

Pick B = 1, then B ∈ N

    assume n ∈N

        assume n ≥ 1

            then 3n2 + 2n ≤ 3n2 +3n2 + 2n * n

                                   = 5n2 = cn2

            then 3n2 + 2n ≤ cn2

        then n ≥ B → 3n2 + 2n ≤ cn2

     then ∀ n ∈N, n ≥ B → 3n2 + 2n ≤ cn2

Then  ∃ ∈R+, ∃B ∈N, ∀n ∈N, n ≥B → 3n2 + 2n ≤ cn2

Then   3n2 + 2n ∈ O(n2)

Then we may face to some cases that are much more complicate. Like to prove:

7n6-5n4+2n3 ∈O(6n8-4n5+n2)

The general step is to assume n  ≥ 1 # As it is applicable in most cases

Then we overestimate the upper bound and  underestimate the lower bound.

So if A < B, and the relation is not really clear, we prove it by using

(A<C<D<E<F<G<B) which the relation of every two of these are obvious

In this case: 6n8 - 4n5 + n2 > 6n8 - 4n5  > 6n8 - 4n8 > 2n8 * 9/2 > 9n6 = 7n6 +2n6 >7n6 + 2n3 > 7n6 - 5n4 +2n3

Disprove of O(n) follows the same pattern. We first negate the initial definition of O(n) and prove the negation is true

Let's think about the case of：

9.2 Big O proof with limits