Week 10: The Big Oh, Omega, and Theta

So this week I am trying to better understand the different symbols that we went over so far in class. I will be
presenting the definitions from the course notes and example for all definitions with some graphs to get a good visualization of what the definition means.

Lets assume we have a function  f(n) = 3n^2 - 2n + 5 and g(n) =
4n^3 + n^2 - 3n + 3
for all definitions below.

The Definition of Big-Oh





The claim is f(n) is in O(g(n))? We can show this by making a graph of the two functions and then seeing if we need to multiply g(n) by a constant to make it true for any natural number >= B.

red  is f(n)
purple is g(n)

As you can see the behavior if we were to continue this graph far to the right as much as possible we can predict that the function f(n) will never be able catch up to g(n) after they intersected at a point which could be our break point however it must be of the domain of natural numbers, therefore the intersections are not always considered the break point and both the break point B and the constant c are dependent on each other and could vary on our choice of either one. However the intersection tells us that the B could be any natural number from that point and on wards.  The key point to this graph is that f(n) is bounded above by c*g(n) for any natural number n equal to or greater then the B, break point.


The Definition of Big - Omega

The claim for this example would be f(n) is in Big-Omega of g(n)? by showing a similar graph from above.

red  is f(n)
purple is g(n)

As you can see it looks possible for f(n) can also be >= to c*g(n) where c is a rational number with a significantly greater denominator such as (1/1000) which will cause c*g(n) to never catch up however if we looked at the graph with a bigger scale we will notice an intersection of the two graphs which indicates f(n) will not always be in Big-Omega of g(n) as n approaches infinity therefore

The claim is False


If this seems wrong or if I possibly misunderstood some of the content please leave me a comment and let me know? Also Note, assuming both examples above were True we can also say f(n) is in Theta of g(n)

Thanks for reading

Week 9: Test 2 Is Complete

Just completed the term test 2 and I have to say that it was not bad as I thought is was. 3 proof questions that didn't involve too much time so overall it was a fair test hopefully everyone else thinks they did very good as well. Don't really have much to say this week just enjoying a bit of a break after a long week of mid terms.


 Good luck and thanks for reading.

Week 8: Book-keeping and Time Complexity Proofs

So this week we just went over the book-keeping of programs in order to determine a rough estimate of their run-time in the worst case. however in tutorial for this part of the section the TA did the book-keeping a bit differently then what we learned in class. Which was counting every operator on each line to determine the total steps that happen on every line, but in class wee just looked at every line being just 1 step. I am assuming different people have there own way of book-keeping programs and counting steps. However after  I have seen the solution's to question from the tutorial problems that week I believe my assumption is true.

Also I can definitely see how finding the runtime/# of steps in the worst case can be tricky however after a little more practice I think I will get use too it. Hopefully?

Week 7: The End of Proof techniques and onto Proofs of Complexity

      We are finally done the proof techniques section of the course and have moved on to complexity proofs. I feel like this section is the real major point of taking this course for computer science. Even though all of the previous sections are essential to know before learning this section, they feel like they are only tools to work with for this upcoming section. However we haven't really seen too much yet, however I suspect we will be learning more about complexity proofs next week.

How I currently feel about Proof Structures and a Summary of Proofs we learned so far

    It has definitely been a challenging section in the course since we took our knowledge of logical notation and have learned how to form proof structures using our understanding of logical notation when a for all symbol is introduced we see it as an opponent picking a variable within the specified domain that we have know control over. However when there is an existential quantifier introduced we pick the variable from a specified domain. I find this is a great analogy to learn in order to understand the differences of these quantifiers when forming a proof.

Since not much has happened this week I will just go over the many different techniques we learned in order to prove some claim such as:

• Proof by Contradiction
• Direct Proof
• An Indirect proof (e.i. using the contrapositive)
• Also using other proven claims and theorems to prove other claims (e.i. Number Theory, Definitions of odd and even, and also Definitions of ceiling and floor of a real number )

Week 6: Upcoming Reading Week

Sorry for the late entry on the this about lessons prior to reading week, I've been a little busy this week. I have also looked at the 2nd assignment, but i started to work on this weeks tutorial worksheet and I finished the first question which seemed simple, however i'm not sure about the structuring of my proof where you can just assume an existential claim when it is the antecedent of the entire statement however it is similar to the example in class about n being odd and n squared also being odd. (picture of proof below):

My answer is similar to this except I assumed an existential claim to already be true and i'm not sure if I also have to prove the claim that I assumed before writing the body of the entire proof.

Week 5: Helpful Tips for Proofs

So I would like to start off by saying that this week was more busy than usual since I had two term tests this week and one of them was held during a blizzard at the end of this week. However I didn't go over any of the lessons we learned this week since I was a bit preoccupied with other stuff. But I am willing to put a few tips and questions below relating to proofs.

Questions and Tips: 

• I had one question about a certain word ('Monotonic') that Danny used in his proof this week that describes one of the steps he did to prove the claim. But i ended up looking up the word and then I realized how obvious the word meant because it was similar to the word 'Monotone' however monotonic relates to a consistent sequence or function.

• A tip when defining universal quantifiers in proofs, whenever something is assumed you indent to represent that within that scope that variable or claim is defined in the main body of a proof. A good way to remember this is to think of a python function and how it must list variables within the functions scope as its parameters.  

Week 4: Beginning of Chapter 3 - Proofs

This week we had just finished the assignment and moved on to the next chapter that involves proofs but what i have noticed with reading some of the chapter notes is that it focuses much more on the structure of certain proofs.

Just wanted to mention this because it seemed pretty interesting and I never really thought of  proof having a specific structure. I always thought when someone is trying to prove how a formula works they would just write down logical facts of what is involved with deriving a formula using other known facts that have been proven or are generally known.

So right now proofs seem interesting and the structuring seems reasonable, however I can see how they can also get tricky when actually trying to prove or even disprove a statement that contains a lot of mixed quantifiers within a claim (an example from notes is at the bottom). But so far I seem to be understanding the structuring concepts.