Week 9 - The Big oh continues.

After a week in the introduction of the big-Oh, things starting to get sort out. In week 9,  we started with the counting step of the algorithm. It gets confusing at first with the different variables and loops. However, with more practise and blank staring, it gets easier.

*I had to admit, even with CSC108, I struggle in doing the general counting of steps that involves n and i. 

 Regardless, the addition loops always make the algorithm more complex and more time consuming.  I also noticed that with the increase of inner loops in an algorithm, the number of steps also increases exponentially. However, with loops on the outside, the steps remain linear and no where close to a exponential growth. 

Taking this code from the lecture as example, 

The inner loops make the steps for the worst case increase from a single power n to a second power n^2. It consumes more time and result in higher complexity. Moreover, it also takes more organizing skills to sort and analyze the algorithm. 

In addition to this week, I learned to prove that some function is within the big-Oh of another function. The introduction of Big Oh allows me to check whether a function will lead beyond upper bound. It is sometimes challenging to imagine the different graphs to visualize whether a function will be trapped under another. As a result, it helps me in understanding how different run times and functions interact with each other. It also allows for optimizing the run time for an algorithm by solving the Big oh proofs. 

The proof structure of the problems are quite similar to the proof that was done earlier. Moreover, I consider them to be easier than the once that were proved before since mostly they involve around polynomials which mostly is done by modifying the powers of the 
variables and the comparison. 

Interestingly, I found a slog that expresses a similar feelings towards the introductions of Big Oh. 
http://mengjiayan.blogspot.ca/2014/11/csc165h1-week9.html#comment-form

Overall, the week were sunk in abundant of examples of proofs.