I was surprised by how short and clear the example for proving 3n^2 + 2n in big-Oh of n^2 was. When we started with the proof structure, I made sure to leave a lot of space in between before the concluding line. Then the professor simply wrote the body in 3 lines. I can say that I didn't see that coming. Now that I am looking back at my notes, I can see a large gap of white space in the proof which is filled with doodles to take up the rest of the space.
One thing that was not as clear to me however was choosing the B. I can see we simply choose c to be whatever coefficient is in front of the n^2 after we added up all terms in term of n^2. To try to figure this out, I looked over two of the example proofs where B was chosen to equal 0 in one and 1 in the other. I noticed that in the second proof (3n^2 + 2n + 5 in big-Oh of n^2), that there was a commented part saying that n must be at least 1. So that means B must be based on this assumption made during the chain of inequalities. I also noticed that we tend to choose B = 0 when trying to establish an upper bound for functions without a constant. However, when constants are introduced, B cannot just be 0 anymore. This is from only examining three proofs however, so I cannot simply generalize it.
Overall, I found Week 9 is be much more explanatory than its preceding week. The week was shorter because of the test on Wednesday but I still felt like I learned more in the two days than all other days prior that dealt with big-Oh.
No comments:
Post a Comment