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 )