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...
