Lambda's Upper Bounds

So in the beginning of this arduous journey, I wrote that I am bound by no identifier. Does this also apply to the concept of Big O? Perhaps. If I were to represent some sort of mathematical function, then perhaps I would be bounded by some function of one degree higher than myself.

With the lecture given a couple of weeks ago, our CSC236 class has been once again introduced to not only lower bounds, but upper bounds as well. We are able to know great things about functions if we happen to know its upper and lower bounds. For example, why would I ever want to use an algorithm if I know that its upper bound during a worse-case application is significantly higher than another algorithm? I do not know about others, but personally I prefer my algorithms to run smoothly, consistently and quickly. Thus, by looking at these bounds, I can determine the most effective algorithm for all my needs! Thus I am greatly eager to learn more techniques to make my life easier.

Another interesting thing that we have been spending a lot of time on is the concept of unwinding. This is yet another fun and useful tool to make life simpler. Instead of having to recurse through a recursive function, we are able to generate a closed-form version of an otherwise tedious formula. Consider the case where we have to use a recursive formula for n iterations where n is a really large number. Thus we have to spend the time it takes to use the formula once, m, n times. So we spend m*n time. Instead, we could spend m time in order to unwind the formula once which provides us with a formula that only takes k time, a value significantly smaller than m, to process. Thus this gives us a k*n + m time to solve the same problem! But since k is such a small number, let's say m / 5, then that simplifies the time-spent comparison between the two algorithms. So you have m*n without unwinding and m*(n+5)/5 with unwinding. You can see now that the difference in time can be astronomical if either m or n are really large numbers. Ahhh, what a time saver.

This class has definitely been one of my favourites this term, which is a surprise because I didn't really enjoy CSC165.

Until next time,
-ラムダ