Week 8: Counting Steps, the Worst Case, and the Big Oh proof

What's up everyone, this is Kyle checking in for a week 8 roundup and discussion. This week, we dived fully into the world of sorting and its applications to the logical and mathematical reasoning of CSC165.

We started out by looking at the number of steps it takes to execute a linear search for any list of length n. Calculating the number of steps it took to execute code was relatively simple at first, but counting steps for nested loops was a bit more complicated and it took me a while to actually understand how it was done. Even now I am not completely comfortable with the method, but through reading through the annotated slides and trying to find my own way of expressing how to calculate the number of steps it takes to execute different searches. I did find, however, that the easiest search method to count the steps of was the linear search, which, compared to many other searches such as binary search, has a rather long run time. After that we learned about the worst case of all these searches, which is the greatest possible number of steps it takes to execute the search for a list with length n. We explored the upper bound and the lower bound of the worst cases, also known as big 'Oh' and big Omega, respectively. Finally to round off the week, we learned how to do proofs involving the Big Oh or upper bound. At first I was confused how we would prove something like that, but after seeing the equivalent statement of a big Oh proof, it became much clearer what we had to do. It took me a while to understand how we were to find a 'B' and a 'c' to satisfy the big Oh for different searching methods, but after a bit of practice with simpler examples of code I was able to understand it.

Well, that's a wrap for this week 8 roundup, let me know if how you guys found this week's lectures, and if it prepared you for the term test that came around in week 9. Also, comment below how you all did in assignment 2, were you able to solve those difficult e, d proofs? (1.1 and 1.2) As always guys, words are hard, computer science is awesome, and later days. This is Kyle signing out.