csc165 halt NOV.24th.2014

In last week lecture, we leaned about some functions with "halt"
we know that not all the functions are uncomputable.
infinity is not always equals to infinity. If one infinity has more members that has finite numbers then it should be larger.However, two sets have the same size if they are one to one or onto
one to one is that for every x and y  f (x ) = f (y ) => x = y
onto is that  for every y, there existed a x such that f (x ) = y

 

 

NOV 15th.2014 CSC165 big omega & prove general statement about 2 functions

big omega:
∃C ∈ R+，∃B∈N，∀ n ∈ N,n >=B ⇒ f(n)>=c.g(n)

prove general statement about 2 functions:

I think this is just a little change from the 1function's style.  One more assume for the second function and leads to the conclusion of the connection between the 2 functions.Pay attention to the choice of picking B,C sometimes we use the max or min of the two numbers, of we might use the ceiling or the floor.

 ∀ f,g∈F, (f∈O(h))∧g∈O(h))⇒(f+g)∈O(h)

Prove:
Assume f,g∈F  #Just the old thing
    assume f∈O(h))∧g∈O(h) #Just the old thing
       ∃cf ∈ R+ ,∃Bf∈N,∀ n ∈ N, n>=Bf ⇒f(n)<=cf *h(n)# nearly the od thing ,just a little bit different on the c, which becomes cf(also B) now.
       ∃cg ∈ R+ ,∃Bg∈N,∀ n ∈ N, n>=Bg ⇒g(n)<=cg* h(n)#now the f(n) becomes g(n),which is for the second function.
       Pick C = Cf + Cg,Then C∈ R+
       Pick B = max(Bf,Bg)
       assume n ∈ N ∧ n >=B
            Then (f+g)(n) = f(n)+g(n) <=Cf*h(n)+Cg*h(n)
                                                      =(Cf+Cg)h(n)=Ch(n)#now we can find how to pick C,which is Cf + Cg
      ∀ n ∈ N, n>=B,(f+g)∈O(h)
       ∃cf,cg ∈ R ,∃Bf,Bg∈N,∀ n ∈ N, n>=B⇒(f+g)∈O(h)
∀ f,g∈F, (f∈O(h))∧g∈O(h))⇒(f+g)∈O(h)

NOV 9th.2014 CSC165 big-oh of n^2 maximum slice

prove 3n^2+2n∈O(n^2)

that ∃c∈R+,∃B∈N,∀ n ∈ N,3n^2+2n<=C*n^2

pick C = 5
   pick B = 0
      assume n∈N # generic  intro ∀
          assume n>=B 
                assume n>=B #antecendent
                    Then 3n^2+2n <= 3n^2+2n^2 # 2n <= 2n^2
                                            = 5n^2
                                            = Cn^2    #since c=5
                    Then N>=B ==> 3n^2+2n<=C*n^2
....


prove    3n^2+3n+5 ∈O(n^2)
              <= 3n^2 +2n^2 + 5
              <= 3n^2 + 2n^2 +5n^2 # N>=1   #pay attention  to 5n^2  that n=0
              =10 n^2
              =c n^2