Week 10 [Big-Ω Proof]

Let's review the definition of  Ω(n^2) : a function f(n) is in Ω(n^2) iff there exists c in R+, there exists B in N, such that for all n in N, n>=B then f(n) >= c(n^2). It is the lower bound. From the definition we can find that for big-Omega proof, the most important part is also about picking c and B.

First example we talked in class is to prove n^2+n ∈ Ω(15n^2+3). There are two tips: tip 1:pick B =1 assume n >= 1; tip 2: pick a c small enough to make the right side an lower bound. There are some important tricks: under-estimation tricks: --> remove a positive term ( 3n^2+2n >= 3n^2) ; --> multiply a negative term (5n^2-n >= 5n^2 -nxn = 4n^2) over-estimation tricks: --> remove a neagtive term ( 3n^2-2n <= 3n^2) ; --> multiply a positive term (5n^2+n <= 5n^2 + nxn = 6n^2). For big-O proof, we over-estimate f(n) and under-estimate g(n); for big-Ω proof, we under-estimate f(n) and over-estimate g(n).

Then we proved some general statements about big-Oh. We introduce set F(The set of all functions that take a natural number as input and return a non-negative real number.) in this kind of proof. 

Lets talk about an example Prove for all f, g in F, f in O(g) => g in Ω(f). Intuition: if g grows no faster than g, then g grows no slower than f. Assume f in O(g): n>= B => f<= cg ; g in Ω(f): n >= B' => g>= c'f. We need to pick the right B', c' so try to find the relationship between B and B', c and c'.

Since f<=cg, g>= 1/c*f. So we can pick c' = 1/c B = B'.

Here is the proof: 

There is a very trick proof we talked about in class which is disproof :

 so we proof the negation of the statement. The trick part is to pick n wisely.