Array Based List WS

Based on your understanding of an arraylist, what Big-O do you expect for the following operations:

InsertEnd / Insert at 0 / Insert at middle / Access First / Access Middle Element / Remove from beginning / Remove from end / Search / Find and remove first copy of a value
O(1) / O(n) / O(n) / O(1) / O(1) / O(n) / O(1) / O(n) / O(n)

Test InsertEnd:

Time overall should increase by ~x10 when problem size increases by x10.
The time per element should be more or less constant.
Because 10 times the number of insertions, takes 10x the total time, the big O of insertEnd is O(1).

Test InsertAt0:

Time overall should increase by ~x100 when problem size increases by x10.
Timer per element should grow by a factor of ~x10.
Because 10x the number of insertions takes 100x more time when the problem size increases by 10x, the cost per insertion is O(n)

Test InsertAtMiddle:Modify the code to insert at location list.listSize()/2 (middle). Run timings starting from 5000:

Time overall should increase by ~x100 when problem size increases by x10. Time per element should increase by ~x10.
This is a linear increase in time per operation.

Test Remove:Make dataSize 50,000. Change the second loop (one added in Access Middle) to remove each element from the array by calling removeAt(0) dataSize times to empty the list one item at a time. Compare that time to using removeAt(myList.size() - 1). Is the result what you expected?

removeAt(size-1) should happen in constant time per operation. Scaling up the problem by a factor of 10 should scale up time taken by ~x10.

removeAt(0) should take linear time per operation. Scaling up the problem of a factor of 10 should scale up time taken overall by a factor of ~x100. (10 times the operations, each takes 10 times the time)

Thought Question:

We want to add a remove(T value) function that removes the first copy of given value from the list. What is the bigO if we simply implement that function by calling search and then if the result is not -1, calling removeAt() with the result of the search?

find + remove

O(n) + O(n) = O(n)

Could we write one a single findAndRemove function that was more efficient than separate calls to find and then remove?

We can't beat bigO of O(n).

Imagine we make one function that searches to find the element, then shifts everything from that location over. The find part will have to search from 0 - j where j is first copy of desired value. Remove will then shift items from j+1 - n each one slot to the left. It still has to traverse all n items.