WEEK 8

What I Learnt and Difficulties

This week’s material covered the formal definition of O and Ω, and worst-cases analyses of two algorithms.

The formal definition of O and Ω

At the beginning of the lecture, Larry used a vivid example (chicken and turkey) to show us the definition, which successfully drew my attention and helped me understand them in a short time.

Although I had no problem on understanding the formal definition of O and Ω, I could not recite them correctly and always mixed them up, because they were almost the most complicated definitions I have seen.

In order to avoid mixing them up, I decided to only remember the formal definition of O, and the Ω just had the reverse symbol at the last part. I copied the definition on the paper lots of times and read it out loudly, and finally recited it!

Worst-cases analyses of two algorithms

I was really not good at understanding the worst-cases analyses at first, and had no idea about what sigma meant.

But when I typed all the code into Python, and put the code into visualizer to see how it functioned, it made more sense to me. The analysis in Ana’s slog also helped me a lot (http://anadamnjanovic.blogspot.ca/2014/11/week-8.html). I knew we calculated each loop’s running time, and add them together (inner loop first, then the outside loop). And do not forget to add the step “line 1” and “loop guard” in the end.