Week 9: big-Oh and big-Omega (updated!)

Week 9 had us busy working on proofs again, now looking more in depth at big-Oh and big-Omega.

One thing I've found interesting in this course has been the way we take a concept that is superficially simple and break it down into its complex parts. That is, taking something one may simply take to be true because it just is and finding out why. It's part of what I love about mathematics and computer science: the discovery of why. Once you understand the logical reasoning behind stuff, it becomes so much easier to conceptualize, and then you can extrapolate what you've learned in all kinds of interesting ways.

For instance, last week we began to really investigate big-Oh for functions, and - while it took some headscratching - I feel like I know understand the underlying implications of writing speedy code now, which I had just accepted in 148. And while it's still a fair bit of hand-waving when it comes to restricting variables, it's clear to see from class what's happening at an abstract level in the call stack when we write more or less complicated code.

So, for instance, when dealing with our max_sum(L) slices, we can try to find a way to reduce the runtime once we actually have a sense of how it works. We know that the maximum slice of L will contain the largest value of L and that if we find the single largest value (worst-case runtime n), then we can determine what to do.

UPDATE:

Adding to this post as I find myself thinking about big-Oh again with A3.

big-Oh and big-Omega became a billion times funner for the dopamine part of my brain once we started applying them to these polynomials. There's a deep inner satisfaction, like fitting together puzzle pieces, that comes from meshing 2 functions together, and it was very fun to experiment with that for A3, where we dealt with oscillating functions.