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.

Q2 Determining Complexity Class

Q2.1

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.

Q2.2

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.

Q2.3

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 where 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.

Q3 List ADT's and Data Structures

Q3.1

• (true) stores an ordered sequence of elements: This was part of our definition of the List ADT.
• (not true) must have a predetermined size during initialization: We said that the List ADT will be a list of variable size.
• (not true) ArrayList and LinkedList are concrete data structures. ADTs can't implement a data structure, it's the other way around.
• (true) can remove or add elements from any position: This was part of our definition of the List ADT.

Q3.2

• For add at the front:
  • The ArrayList needs to shift all the elements over which is a linear operation since you have to loop over all the data.
  • The LinkedList just needs change the front pointer and make the new node point to the old front. This does not require looping over all the data, so it will be constant time.