Wednesday 3 December 2014

Week 10: Big Omega, Big Theta, General Properties about Bound Proofs, and a Little about Limits

What's up guys, this is Kyle here checking in for a weekly wrap up of week 10 of CSC 165. Finals are drawing near for this course as there are only 2 more weeks of class left. Hope everyone is following along so far. This week we covered quite a bit of new concepts, it was definitely a little bit overwhelming to wrap my head around. We started off covering how to incorporate limit laws and L'Hopital's rule when proving Big O. We then moved on to learning how to prove Big Omega, which in all honesty, wasn't that difficult because of the similarity to the proof structure of Big O. This was followed by learning how to write a new kind of bound proof which was Big Theta, which essentially combined the pieces of Big O statements and Big Omega statements into one statement. Finally, to round up the week we went over some general properties about upper bounds and lower bounds. So, now that I've set up a stimulating intro, let's get into the juicy details.

We started the week off by going over some week 9 things that we did not get to tackle during the actual week 9, which focused on using limits as an option to solve proofs about Big O of certain functions. This technique was mainly used to be able to prove any Big O statements involving exponential functions. This is because there is a statement about limits of the rationalization of the two functions involved in the proof as x (or n) approaches infinity that closely mirrors the statement about Big O in terms of structure. This can be used to help us write a proof on the Big O of these particular functions. This was initially hard to understand at first, but because this concept needed to be used to complete assignment 3, I looked into the course notes as well as the annotated slides in order to fully grasp this idea, and it worked. I now feel completely comfortable with using limits to solve Big O proofs. Next up, we tackled writing proofs about Big Omega and Big Theta, which basically had the same proof structure as Big O except for one difference. In the case of Big Omega, instead of a function f(n) being < (c) g(n), it was now f(n) > (c) g(n). Big Theta essentially combined these two statements to say there was a (c1) g(n) < f(n) < (c2) g(n), essentially saying that g(n) could be bounded above and below f(n). Like I stated before, because this concept was very similar to Big O, it wasn't at all hard for me to understand it right away. Finally, we ended the week by going over general properties about Big O and Big Omega of multiple functions, and how to tell without looking at the actual function whether the statement was true or not. An example of this is that we were able to prove that for all functions f that can be bounded above by g, the square of f can also be bounded above by the square of g. Once again the proofs for these concepts were very straightforward and didn't cause any headaches for me.

To conclude it all, this week was packed full of information, but thankfully all the information was easy for me to understand. If even one of the concepts proved to be difficult for me to grasp it would've definitely be a excruciating week. As it was it was pretty challenging not because of the difficulty of the concepts but simply because of the amount of information we were taking in. But what do you guys think? Did you think we learned a lot this week? Were you all able to follow along or did you lag behind at some parts? Let me know in the comments below the answers to these questions as well as any other things you want to say. Let's start a discussion. Anyways, that about wraps up this report, as always, words are hard, comp-sci is awesome, and later days. This is Kyle signing out

No comments:

Post a Comment