Remember, "the answer" is only half of it! Also, make sure everyone in your group can explain why.
We will use this Gradescope Online Assignment as our worksheet for in-class work. These problems are coded as being worth points for our simplicity, but will not impact your grade in the course.
Notice that we have nested loops here that both run
n times so we know there should at least be a $n^2$ involved in our run-time. Since all the other work inside the loops is constant work, the overall workload would be proportional to $n^2$ which we call quadratic.
You might be a bit concerned about the presence of an
if statement there. Since the body of the
if statement is constant work, then the whole
if block is just constant whether or not you enter the
if condition. In other words, it doesn't really matter! This problem would have been too hard to analyze if the body of the
if statement did some other looping.
Here we have two loops in sequence rather than nested loops. Each one of these loops individually would run in linear time (they do some constant work nn times). We first run one loop and then run the other for a total workload that would be linear overall.
⭐️ Edit after class: This is only guaranteed to be linear if the body of the loop is constant time. This would only be true if the call to
get(i) was a constant time operation (which is not true for
LinkedList). If a
LinkedList would pass in, suddenly this would have an overall quadratic run time! We added an assumption to this problem so that linear is the right answer.
It's a little tricky to analyze the body of this loop and the loop itself separately. If you look at what this loop is doing as a whole though, you can convince yourself that it will run at most three times no matter how large
n is. Why is that?
The loop will
break once it reaches a number
i % 3 == 1. The value of
i % 3 only has 3 possible values (0, 1, 2). As our loop decreases
i it will cycle between these values, eventually hitting
i % 3 == 1, thus breaking out of the loop.
addat the front: