CST370: Design and Analysis of Algorithms, Week 2

Week 2

This week was spent analyzing algorithms and discussing Big O, Big Theta and Big Omega, along with recursive algorithms. 

I am fairly confident in my understanding of the differences between the three notations. The way I have been keeping track of each is that Big O means "this or better," Big Theta means "this is it," and Big Omega means "at least this." Big O gives an upper bound, Big Theta is the tight bound, and Big Omega gives a lower bound.

Where I am still having trouble is confidently looking at code (or pseudocode) and connecting it to one of the growth rates. I understand the definitions when written out, but when I am given an algorithms, I have to slow down and figure out what the basic operation is, how many times it runs, and what happens to n each time. 

I also had difficulty with backwards substitution. I understand the general idea, but seeing all of the M(n-1) and M(n-2) examples with the substitutions made it difficult to keep up. I need more practice before I can confidently do it on my own.

Overall, this week was definitely more challenging than Week 1. With more practice and working through examples, I hope to become more confident with the material.