Consider the two files Attached below and answer the question below the code.

File: ArrayList.java

public class ArrayStringList implements StringList {

String[] elements;

int size;

public ArrayStringList() {

this.elements = new String[2];

this.size = 0;

}

public void prepend(String s) {

expandCapacity();

for(int i = this.size; i > 0; i -= 1) {

this.elements[i] = this.elements[i - 1];

}

this.elements[0] = s;

this.size += 1;

}

public void add(String s) {

expandCapacity();

this.elements[this.size] = s;

this.size += 1;

}

public String get(int index) {

// TODO: Check for out-of-bounds

// throw IndexOutOfBoundsException

return this.elements[index];

}

public int size() {

return this.size;

}

private void expandCapacity() {

// NOTE(joe): I changed currentSize to currentCapacity below

// because it's a better name for the variable

int currentCapacity = this.elements.length;

if(this.size < currentCapacity) { return; }

String[] expanded = new String[currentCapacity * 2];

for(int i = 0; i < this.size; i += 1) {

expanded[i] = this.elements[i];

}

this.elements = expanded;

}

}

Answer the following questions, and justify them with one or two sentences each:

• Give a big- bound for the best case running time of prepend in ArrayStringList
• Give a big- bound for the worst case running time of prepend in ArrayStringList
• Give a big- bound for the best case running time of add in ArrayStringList
• Give a big- bound for the worst case running time of add in ArrayStringList

In all cases, give answers in terms of the current size of the list, and assume that the list has some non-empty size n. That is, you shouldnt consider the empty list as a best case; instead think about the best case based on other factors like size, capacity, and nodes.

Notable points to consider:

• Creating an array takes time proportional to the length of the array
• When considering the running time of a method, make sure to take into account any helpers methods it uses!