Big-oh of polynomials--Week 9

This week we introduce the big-Oh of polynomials. First, we introduce what is big-Oh O(n^2)? It is a polynomial function that  take a natural number and return a positive real number such that
 cR+,  BN, N, n>=B, 3n^2+2n<=c(n^2). This may look hard to understand, so we can give a simple example of big-Oh proof.

Prove 3n^2+2n O(n^2)

 cR+,  BN, nN, n>=B, 3n^2+2n<=c(n^2)

Pick c=5 ,then CR+
pick b=0, then  BN
assume nN,
    assume n>=B
         then 3n^2+2n<= 3n^2+2n^2
                                 =5n^2
                                =cn^2



     then n>=B ⇒ 3n^2+2n<=cn^2
then BN, then n>=B ⇒ 3n^2+2n<=cn^2
then  cR+,  BN, nN, n>=B, 3n^2+2n<=c(n^2)

Counting Time Complexity--Week 8

This week we start to learn the interesting and harder staff-----Time Complexity.

I will give a simple linear search python function to talk about the time complexity.

ex:

def  LS(A,x):
       '''Return an index i such that x==L[i]. Otherwise, return -1.'''
       i=0                                 (Line 1)
       while i<len(A):             (Line 2)
              if A[i]==x:             (Line 3)
                    return i             (Line 4)  
              i=i+1                      (Line 5)
       return -1                        (Line 6)

so, if we give an input (A=[2,4,6,8], x=4), what will the time complexity be:

we can trace our code like this:

Line 1: 1 step (i=0)
Line 2: 1 step (0<4)
Line 3: 1 step (A[0]==4)
Line 5: 1 step (i=1)

then again, we go to while loop

Line 2: 1 step (1<4)
Line 3:1 step (A[1]==4)
Line 4: 1 step ( return 1)

so our python function ends here, if we count the total time complexity, it will be 1+1+1+1+1+1+1=7 steps

We can even turn this question into a harder question: what is the worst case in which x isn't in A?

then we can think like this :
line 1 : 1 step (i=0)

while loop : 3* n   (line 2,3,5 executes once for each 0 to len(A)-1 , which line 2,3,5 executes once for n times)

then we have 2 more steps to add, which is last while loop check and the last line 'return -1')

so in worst case, the time complexity is  3n+1.

Inference Rules-Week 7

Up to today, we have learned some rules of inference to allow us to reach conclusions about certain situations. Here are some of them:

Conjunction Elimination: if we know A^B, we can conclude A and B are both True.

Existential Elimination: if we know that there exist a belongs to X, P(a), then we can certainly pick an element with that property. Pick a' belongs to X, then p(a').

Disjunction Elimination: if we know that A V B, and we know that not(A), we can conclude that B must be True.

Implication Elimination: if we know A implies B, and we also know that A is True, we can conclude that B is also True. On the other hand, if we know not(B), we must conclude that not(A) must be True.

Universal Elimination: if we know that for all x belongs to X, P(x), then if we choose any a belongs to X, we can conclude that P(a) must be True.

Implication introduction:if we assume A and then B follows, then we can conclude that A implies B

Universal Introduction: if we assume that a is generic element of D, and we derive P(a), then we can conclude that for all a belongs to D, P(a).

Existential Introduction:if we can show that x belongs to X, P(x), then we can conclude that there exist x belongs to X, such that P(x).

Conjunction introduction:if we know that A and we know B, then we can conclude A^B

Disjunction introduction: If we know A, we can immediately conclude that A v B

Proof By Cases---Week 6

Sometime, it is more convenience to prove some proofs by cases. Consider the following proof:

"for all n belongs to N, n^2+n is even"

in order to prove above, it is more convenience to consider the case where n is odd ,then the case n is even.

First, we consider n is odd, then we can use definition of odd to assume n is of the form n=2k+1,where k is natural number. Then n^2+n=(2k+1)(2k+2)=2(k+1)(2k+1)=2m ,where m is a natural number of the form m=(k+1)(2k+1), therefore by definition  n^2+n is also even.

second, we consider n is even, then we can again use definition of even to assume n is of the form n=2k, where k is natural number. Then  n^2+n=(2k)(2k+1)=2n ,where n is a natural number of the form n=k(2k+1), so by definition n^2+n is also even.

So, no matter n is odd or even, we conclude that n^2+n is  even.

Finally, proof by cases are  good techniques that can make some proofs become so easy , therefore we need to know when or how to use proof by cases in the future.

proof from different directions--Week 5

proof from different directions:

ex:
Prove: for any natural number n, n^2 odd implies that n is odd.

if we start to assume the domain and the antecedent, we may write like this:

assume n is typical natural number.
assume n^2 is odd,
then exist k belongs to N, n^2=2k+1

and from above we want to show that n is odd.

we may find that it is almost impossible for us to proof the case n is odd from n^2 is odd.

However, we may use the fact that the contrapositive of the original statement and the original statement are equivalent, so if we can proof the contrapositive of the original statement, we will find it is much more easier.

which is n is even implies n^2 is even

For _All_Exists and Exists_For_All--Week 4

Here is one example of python code  to show the differences between for _all_exists and exists_for_all

let S1=S2={1,2,3,4}

def forall_exists(S1,S2):
      return all({any({x+y==5 for y in s2}) for x in S1})

def exists_forall(S1,S2):
      return any({all({x+y==5 for y in S1}) for x in S2})

the first python function will return True, since for all x in S1(x=1 or x=2 or x=3 or x=4), we can find one instance of y in S2 that satisfy x+y==5. (if we pick x=1 ,we can choose y=4 such that x+y=5. if we pick x=2, we can choose y=3 such that x+y=5 and so on)

So the statement inside the all will return True. (all{True, True,True,True} return True) ,therefore the first function will return True.

what second function saying is that for all x in S2,  then for all y in S1, x+y=5. we  find each time we choose x, we can pick a y that make x+y=5 false. for example, if we choose x=1, then we pick y=1, then we see that x+y=5 is false). So the  function will have the result any{False, False, False, False} in which will return  False

More on negation-- Week 3

As i mention in Week 1's blog, negation means negative of the original 

statement. In this week, we put all the universal  , existing quantifier 

and implication together and we try to negation them all  at once. Here 

is one example:

¬(∀ X∈R, ∃ y∈R, P⇒Q)⇔  (∃ x∈R, ∀ y∈R, ¬(¬PvQ) )
(∃ x∈R, ∀ y∈R, P^ ¬Q)

although, negation of such long statement seems to be hard at the beginning, 

but after many times practicing the negation, it becomes pretty computational 

and easy.