Week 8- Formal definition of big-Oh and its proof structure

        In this week's class, I was taught the formal definition of O(f(n)), which is referred to as the asymptotic upper-bound:

By categorizing a function as O(f(n)) means that the function grows no faster f(n). And this definition simply means beyond breakpoint B, the function g is upper-bounded by f(n).

        An example is to prove that the function f(n)=2n^2 + 1 is upper-bounded by n^2:

The detailed proof structure for this is:

Because the definition for upper-bound begins with there exists, my first line for the proof begins with choosing a c' and a B'. However since I do not know how the proof will turn out, I left the values for c' and B' blank for now. I then proceed to the next line by stating that the values I chose for c' and B' matches their given domain. I then assume a generic natural number n because of its universal quantifier. On the same line, I also assumed the antecedent to be true. Then I squared the antecedent. Since I want to arrive at the equation that 2n^2 + 1 is less than or equal to cn^2, I made B' equal to 1 for simplicity. Hence n^2 is greater than or equal to 1. Because I chose a value for B', I go back and fill in the first line with B' = 1. And since 1 is a natural number, my choice is applicable.  Then, I added 2n^2 to both sides of the inequality, and simplified it to 2n^2 + 1 is less than or equal to 3n^2. Now, it is obvious that in order to prove  2n^2 + 1 is less than or equal to cn^2, all I need is to make c' equal to 3.

        In conclusion, during tests, it is much easier to figure out a value for B' and c' on a piece of scrap paper before writing the formal proof. This is because with more complicated examples, I might have to constantly change my approach.

Week 7- Algorithm’s time complexity

        In week 7, I was introduced to a brand new concept of sorting algorithms and their complexities. Statements, such as “the worst-case runtime of bubble sort is in O(n^2),” that used to make no sense, now made perfect sense to me. However, I have to admit that calculating the worst running time is the hardest part in this course so far.

        To begin, “running time” in computer science does not mean the length of time in which an algorithm is run, rather, it means the number of steps that the algorithm takes to run. And sometimes, the number of steps an algorithm takes to run depends on the size of the input (which is often referred to as n). For instance, a program may take a running time of 2n steps, and another program can take nlogn times to run. However, the number of steps is not important since we only care about the change in running time as input size varies. Hence, constant factors of running times do not matter, only the highest-order term matters, which means 2n^2 is no different than 301n^2 since they are both in the category of n^2  running time.

    The hardest part of this week is to compute the running time for the worst case. By definition, the worst case time complexity of P with input X (in the set of I) of size n is:

And when counting the steps, it is much simpler to break the program into separate parts and then evaluate the number of steps required for each. In general, a return statement requires one step; an if-statement requires at least two steps, where one has to be the evaluation of the condition of the if-statement, and the other steps are the lines to be executed if the condition of the if-statement is satisfied; an assignment statement requires one step; a variable or constant evaluation also requires one step; and arithmetic, comparison or boolean operators also each require one step. Lastly, break the program into simpler parts by letting while loops be a separate entity. After the separations are done, add up the number of steps for each part under the worst-case possible. One thing to keep in mind is to figure out the number of times the while loop iterates as the input size varies. 

An example of linear search:

Line 1 is an assignment statement, so it is evaluated into 1 step. line 6 is a return statement, so it is also evaluated to be 1 step. In the worst case possible, given that len(A) == n, the while loop is iterated exactly 3n times plus one extra step in which the while loop condition is evaluated to be false. To be more specific, with an input size of length n, i is incremented from 0 to (n-1) (since if i = n, the while loop condition would return false), which means the loop is iterated n time. And within the while loop, there are 3 lines. However, in the worst case,  the x that the program is looking for will not be in list A, thus, line 4 will never be executed. This means with each iteration of the while loop, line 2, line 3 and line 5 are evaluated each time. Line 2 is always evaluated because its the while loop condition. Line 3 is always evaluated because it is the if-statement condition, and it will always evaluate to false. Line 5 is evaluated each time because it is an arithmetic operation. This means that in total, with an input size of length n, the while loop contributes 3n steps. However, one cannot forget one last step in which the while loop condition is tested and is evaluated to be false (where i = n), which in turn leads to the return statement in line 6. Thus, in conclusion, the worst case occurs when x is not in list A at all and  WLS(n) = 3n + 3.

Week 6 - Proof by cases

        In this week, I learned about proof by cases, proofs with multiple quantifiers, and proofs involving definitions such as limits and floor. To begin, proofs with multiple quantifiers are no different than having only one quantifier, since the proof statement for “for all” will always begin with “assume…” following an indentation for the second line, while the proof statement for  “there exist” will begin with “pick x= …” with no indentation in the following line. Moreover, proofs involving manipulation of the definition of limits are also very straightforward, since the definition of limits and its epsilon-delta proof are already taught in MAT137. As for the definition of floor, ample examples and solutions are being supplied by the professor. Hence, the only difficulty I encountered in this week is only the topic of proof by cases.

        The reason for my lack of confidence in proof by cases is that the number and type of cases vary depending on the statement itself. No matter how many examples I am taught, the type of cases I encountered are all different. Hence, I was afraid that I might miss a case and forget to consider it during a test. Due to this doubt, I have gathered some tips concerning proof by cases.

        In general, when proving a formula using proof by cases, I have to first split my arguments into different cases while covering all possibilities, then prove the conclusion for each case. For example, when proving x^2 + x is even for all integers x, I have to prove for 2 cases, where one is x is even and the other case is x is odd (since x^2 + x is factored into x(x + 1) which means one of the factor has to be even while the other is odd). Another example where proof by cases is used is when proving “something equals to another thing”. In this situation, I have to prove two cases, where the first case is “something >= the other thing”, and the second case is “something <= the other thing”. By proving both cases are true, I can conclude that the conjunction of the two cases yield equality (=). Furthermore, some tips for generating cases is to break up the domain D into D1 U D2 U D3 U….U Dn, in which the number of cases is n. Lastly, the “Law of the excluded middle”, which states that a formula can only be true or false and nothing in between, can be introduced in my proof so that I can split P into two cases depending on whether it evaluates to true or false (P V not P).

        

Week 5- Prove Using Contradiction

        This week, I was taught different types of proofs such as proof using contrapositive, proof using contradiction, proof for existence and proof about sequences. Among them, the hardest to grasp and understand is proof by contradiction. At first, I don’t know how to establish a contradiction and when should I apply it in proofs. However, as more examples are being shown in class, I realized that there is no such thing as the perfect timing to use proof by contradiction, because it can be used whenever. 

        Generally, proof by contradiction is used when I want to prove the conclusion without establishing or knowing anything about the antecedent. To be more specific, to arrive at a possible contradiction, I first have to identify the statements that I already know is true. Then I prove “P implies Q” by transforming the implication to its contrapositive, which is “not Q implies not P” and assume the conclusion (Q) to be false. I then write down some steps that leads to “not P”, which thus proves that a contradiction exists since P is previously established to be true.

        A quick example to demonstrate proof by contradiction is to prove the statement “there are infinitely many natural numbers.”. First, to derive a contradiction, assume that there is a finite number of natural numbers (which is not Q). If this supposition is true, then there must exist a largest natural number x such that no other natural numbers are greater than it. However, a contradiction is generated since if I double x, I get another natural number y = 2x (y is a natural number because natural numbers are closed under multiplication) that is greater than x (since 2 > 1). Hence, there does not exist a largest natural number x, and I arrived at a contradiction by assuming not Q. As a result, the statement “there are infinitely many natural numbers” is true.

        In conclusion, proof by contradiction is a great technique to use when one is not sure what the antecedent is in the statement. 

Week 4's Transitivity

          In class, we were introduced to the topic of transitivity. This idea simply means that if a ⇒ b, and  b ⇒ c, then a ⇒ c. As simple as this idea may sound, the professor asked the class to negate the statement:    

and simplify it by transforming all implications into disjunctions as a way of proving the entire original implication to be true. Personally, this is the hardest part of Week 4’s lessons since it involves  De Morgan’s Law and many other laws we learned in the previous week, such as the distributive laws:

The other difficulty in simplifying the negation is that the notations become really messy as the implication gradually breaks down into disjunctions. Hence, it was very hard to not make a mistake. In my picture example, I negated the implication by changing the P --> Q to P or not Q following De Morgan’s Law. On the third line, I changed P ---> Q into its equivalent statement not P or Q. I also simplified the negation of the last bracket by employing De Morgan's Law. On the fifth line, I expanded the equation using a similar approach to FOIL in math class. Since all statements are conjoined by or's, Q or not Q is omitted from the equation since it is false. (recap: false or true yields true, however false and true yields false.) On the last line, since all three statements are false, the negation of the original statement is true. Hence, the original implication is true.

        To sum up, the most challenging part about this week's class is to simplify or change the original statement using De Morgans law, distributive law and etc. One mistake during computing could lead to a completely different conclusion. This reminds me that I have to be more careful during future tests.