The concept of Big-Oh can be quite terrifying if you don't really understand it at first. However, after more rigorous overview of course notes and reading students' slogs about Big-Oh, I felt much more comfortable with this concept and now I know why it is such an important concept for computer science students.
Refer to 1i's March 21st, 2013 slog post : http://oneicsc165.blogspot.ca/
In this course, we've been dealing with proofs for a while now and it is fairly easy to just focus on the the structure of the proof, the symbolic statement of the proof, and the math involved in linking the antecedent to the consequent. However, because it is fairly easy to do this now and it almost becomes an automatic thought process, it becomes fairly easy to forget about what each line actually means outside of all the math and steps.
This is why I liked 1i's approach at understanding exactly what Big-Oh means by going through and understanding each step of a proof. If you understand what each of the relevant lines of the proof mean instead of just performing the steps to finish the proof, you'll have a better understanding of Big-Oh.
Through each step, 1i continuously reminds us that we are making our function f(n) that is bounded by our function g(n), bigger and bigger and eventually it is shown that a constant multipled by function g(n) is still bigger in the end. This is what it means to have an upper bound and this is what Big-Oh means. Through the proof, which I initially thought was just some mathematical equations, operations, inequalities, etc that would not give us a bigger/real world picture, and through 1i's slog post, I now have a better understanding of what Big-Oh actually means.
Thanks 1i for your post!
No comments:
Post a Comment