2014年11月9日星期日

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

没有评论:

发表评论