Friday 31 October 2014

Week 8

This week we learned about counting steps, worst-case, and formal big Oh. We learned a formal definition of O(n^2) and we were presented with a useful example of "chicken size" being in O("turkey size") because after a Breakpoint the chicken will always grow and or be smaller than the turkey. I learned that when proving that a function is an element of O(n^2) you use the definition of O(n^2) and pick a c and a B. I find that the definitions we have learned in this course generally are useful in the proofs that relate to what they are defining. There is also a definition for the lower bound of a function where the formal definition switches a part of the upper bound equation by making what was f(n) <= cn^2 switch to f(n) >= cn^2. We learned more about counting steps and analyzing a sorting algorithm. I figured out the difference from last week of wost case scenario and time complexity, which was confusing me before. I also realized in the worse case scenario, where a while loop and iterations over a list are normally involved, that the letters are placed in regards to the size of a list that will be iterated over. I learned that the worst-case scenario with lower bound can be found by multiplying n/3 for each loop it goes through. As in each segment of a while loop it has.

No comments:

Post a Comment