Mingyu Liu @ CSC165H1 SLOG8
After term test two, we are having an
exercise lecture, which involves exercises of big-oh proof and proof by using
limit techniques. In this week’s slog, I would like to recapture the examples
of this week’s lecture.
In order to prove big-oh, we have to
understand the definition once again from last week’s lecture which is shown in
this image:
This means that beyond the break point B,
f(n) is upper-bounded by cn^2 which indicates that f(n) is grown slower than
cn^2.
When we
grasp well the definition of big-oh, it is time for us to learn further
according to big-oh:
This is
a notation of O (n^2) being a set of function which consist of two parts
exactly. The first one is that functions that take in a natural number and
return a non-negative real number.
The second
one is known as the definition of big-oh which means that beyond the breakpoint
B, f(n) is upper-bounded by cn^2. As a result, if you want to prove big-oh
correctly, the set of functions in the first criteria must satisfy the second
criteria.
Exercises:
1: c
should be larger than 3, because the constant of the highest-order term.
2: when
n = 1, 3n^2+2n = 3+2 = 5 = 5n^2
Therefore,
B=1 and c=5 is good to solve the problem.
3n^2 +
2n : N -> R ^>=0 #3n^2+2n >=
when n is natural number
Pick c=5,
then c is belonging to R+ #5 is a positive number
Pick B =
1, then B is belonging to N # 1 is a
natural number
Assume n is belong to N
Assume
n >= 1
Then 3n^2 +2n<= 3n^2 +2n *n
=5n^2 = cn^2
Then 3n^2 +2n <= cn^2
Then n>=B -> 3n^2 +2n <= cn^2
….introduce
antecedent and quantifiers (omitted)….
When we
know how to prove big-oh, disprove seems important for us.
First,
we have to negate it:
Then we prove the negation and the process
is like I did in the previous exercise.
In conclusion, in this week’s lecture, I believe
I grasp well on proving and disproving big-oh, but the only thing I have to
work on is proof of big-oh by using limit techniques which I will illustrate in
next slog.
Eighth slog
Mingyu Liu
没有评论:
发表评论