Fall Break

This past week we have continued to expand our knowledge of big O and big Theta.  The proofs do not seem very hard when you think about what is actually happening.  I find it very useful when Danny makes a diagram showing what the proof is actually trying to say because after all understanding what you are trying to prove is the most fundamental step.  The way I think about big O is that it is the most practical way to compare the efficiency of algorithms.  It is more about categories than being precise.  Since larger exponents overpower smaller ones by such a large amount, regardless of the constants, it is all that you really have to look at.  This fact can be seen in other places of mathematics as well such as evaluating limits going to infinity.  I think the truly hard task would be calculating the average efficiency of algorithms, I am not even sure how it would be done.  In fact my TA told our class that there are a few professors at U of T who have devoted their entire careers to studying average efficiency.  Stealing from some of the ideas of business you know that the overhead or fixed cost would stay constant, its just a question of how you would calculate the total variable costs.  Perhaps we will learn more about this in CSC236.