## Obtaining better asymptotic performance for a list

Abstract: This course is greatly concerned with characterizing the performance of a given approach or algorithm.

In this exercise, you

• develop an implementation of a list for which adding to its end takes O(1) time
• measure the time of appending to lists with and without your improvement
• develop a method for determining the size of a list in O(1) time.

Goals:

• To appreciate that a simple change to a data structure can have a dramatic effect on performance.
• To appreciate that the concepts we study in theory, namely asymptotic time complexity, is actually observable in practice.

## Warmup procedure

• Set yourselves up as usual for studio, with one person having eclipse open, and others with these directions.
• In eclipse,
• right (control) click on your project name in the package explorer
• Drag down to Team
• Choose Pull

## Useful prepping information for this studio

• This video is from CSE131 and it shows conceptually how to add to the end of a linked list.
• Here starts the roundtable discussion with code about how to add to the end of a list.
• You are given this code for studio, but it's important to understand how it works.
• Sequence through clips 5 and further to see the rest of the implementation.

## Part A

• In the studios source folder, in the studio2 package, open the AddLastNoTail class.
• Run that class as a Java Application
• The work performed here is mostly in the AddLastBase class.
• Take a look at its run method, where you'll see the code that appends n times to the end of a list.
• The AddLastNoTail extension you run here uses a list without a tail reference.
• Your run will generate ticks and timing in the outputs folder, as usual.
• Open and plot the data you see in both
• The code for adding to the end of the linked list can be found in the LinkedList class in the studio2.lists package.
Part A

Write answers to the following in the studio2.txt file of the studiowriteups folder:

What do you see in the plots for ticks and time?

How would you characterize those curves?

Based on the code you see, based on your understanding of how we are currently adding to the end of a list, and based on your work from Studio 1, why do you see the results you see for ticks and timing?

## Part B

• Find and open the AddLastWithTail class. This is the class you run to generate the ticks and timing results.
• Find and open the LinkedListWithTail class in the studio2.lists package.
• This is the only class you will modify in this exercise.
• As given to you, its behavior is identical to AddLastWithTail.
• As a group, and with help from your TAs, modify this class so that it uses a tail reference, which always points to the end of the list.
• If we take the above statement as an invariant, then every method must leave tail so that it does point to the last element of the list.
• This must be true after the constructor finishes.
• It must also be true after addLast finishes no matter what path is taken through that method.
• Run AddLastWithTail and look at the ticks and time plots.
Part B

What behavior do you see now for appending n items to a list if you use a tail reference?

While we have reasoned so far only about time, if we are adding n elements to the end of a list, what is the asymptotic complexity of the additional space required when using the tail reference?

Under what conditions would you recommend using a linked list with a tail reference vs. a linked list without at tail reference?

## Part C

For this part, you continue modifying only the LinkedListWithTail class.
We next look at the expense of determining the size of a list of n elements.
• Run the Size class and look at the ticks and outputs.
• Look at the getSize() implementation.
• Discuss in your group and with your TA how it works.
Have you convinced yourselves that it takes the time it should?
Part C

Why does getSize() take the ticks it does?

OK now for the fun part…
• There is a relatively simple way for getSize() to take Θ(1) ticks.
• Implement your idea and rerun Size.
Part C, continued

How did you achieve Θ(1) performance for getSize()?

## Part D

Let f(n) and g(n) be non-negative functions of n.

• If f(n) = O(g(n)), is it true that f(n)+g(n)=Θ(g(n))?
Recall the approach for showing that one function is Θ of another: You have two obligations here:
• Show ∃ c ∃ n0 | ∀ n≥n0 f(n)+g(n) ≤ g(n)
• Show ∃ c ∃ n0 | ∀ n≥n0 g(n) ≤ f(n)+g(n)
and you can assume that f(n) and g(n) are non-negative and that f(n)=O(g(n))
• If f(n) = O(g(n)), is it true that f(n)/g(n)=Θ(1)?
Try to come up with proofs of the above.

• If there is a file for you to complete in studiowriteups, please respond to the questions and supply any requested information.
• You must commit and push all of your work to your repository. It's best to do this from the top-most level of your repository, which bears your name and student ID.