Below is a problem from an Algorithms assignment that I had to complete this evening. The instructions were to calculate the best case and worst case running times for the function. Because n could be any integer, this required a response in theta notation. Because it is a while loop, the best case is simple, n starts less than 1 and as a result, only the assignment line runs (theta is a constant (1)). I had to warp my brain into a pretzel to even begin considering how to calculate the worst case scenario. I myself could not manage to entirely figure it out, I had to consult my friend Guy, who has a much better grasp of math than I do.
First, to calculate the worst case, we have to acknowledge the best case, which is 1, then we have to add the rest of the method to it. In this case, there were five operations, so we move on to 1+ 5*z, but we have to figure out what z is. My conclusion before Guy assisted was that it had to be more than a constant (1, 2, 3, etc), but had to be less than linear (the size of n itself), which leaves a logarithmic. Only problem is I have only thought in simple logarithmics. Guy on the other hand, threw in a base 2, which suddenly made sense and helped result in the final answer, which is 1+5(log(n)/log(2)). The answer is good enough, but can be further refined to be 1+5(ceiling(log(n)/log(2)) or 1+5(ceiling(log2n)). That wasn’t so hard was it? Honestly, for me it was so mind bending that I couldn’t remember my student ID to put at the top of the document, or my instructor’s name to be able to look up his email address in my address book. I am so glad that assignment is over.
Input: x (an integer), n (an integer)
addStuff4(x, n)
{
i=n;
while (i ³ 1)
{
x=x+1;
i=floor(i/2);
return x;
}
}