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
没有评论:
发表评论