Starting with the difficult part of 1.2
In the algorithm 1.2.1 I don't see how one of the lists ends up being empty.
This is teaching us about the equivalence relation (~) between leading-order coefficients. As I understand it there is a way to state simply what is the difficulty of the algorithm. For example 3x^2 -3 ~ 3x^2. We don't really worry about the lower power terms.
The chapter does a good job at showing how the same outcome can be achieved by two different algorithms. It also shows that one is superior by decreasing the big O leading coefficient.
From chapter 1.1 examples 1.1.10 and 1.1.11 were the hardest to understand but the most useful for understanding how to prove these types of problems. These examples were what gave me the tools to solve the homework proof problems.
I found the proposition 1.1.3 very useful in helping undertand the concepts of big-O and little-0.
I am now realizing that I have more to understand about temporal and spatial complexity since I had difficulty explaining part b) of 1.6 and I have my doubts as to whether I understood the implementation during 1.2. I will make sure to ask more question on the subject in the days to come.
No comments:
Post a Comment