Runtime is the Most Beautiful of Dreams and the Worst of Nightmares - Week 9

This week we continued on with runtime proofs and while I realize the importance of understanding runtime, I continuously struggle with it. While working through the basics of polynomials seems more straight-forward, actually creating the equation based on the code is very difficult for me. While we have had a couple examples in class, it is still hard to see the relationships between multiple while loops in a single function. Some of them seem fairly simple with a run-time of n to the power of however many while loops exist, others are not that simple with a j based on an i and a k that do not behave as expected. In those cases I am not even sure how to begin to understand the relationships between the while loops.

In this week’s tutorial, we had to come up with a formula for a function. I tried to emulate the formula we had done in the previous week. I worked with a couple other people in tutorial and we had all assumed that the middle loop ran for 3n + 1, while the outer loop ran another n amount of times. We tried to multiply them together but the relationship between the two was more complicated. It needed a summation between the two. In the end, the answer was 3n(n-1)/2 + 4(n-1) + 2. While our TA did a good job of explaining why this was the case for this particular example, I believe I would have trouble recreating something similar in the future.  Thus, runtime can be both wonderful and horrible in practice but it can also be this way when trying to calculate the runtime.