Big O Analysis of various implementations of methods for LinkedLists and ArrayLists

# Big O Analysis of various implementations of methods for LinkedLists and ArrayLists ## boolean add(T element) ### LinkedList: O(n) Appending requires the program to iterate through the nodes until you get to the end of the list. This obviously scales as the list grows. ### ArrayList #### Best Case: O(1) When there is space in the array, you can just access the free cell in the array. <a href =https://stackoverflow.com/questions/7297916/why-does-accessing-an-element-in-an-array-take-constant-time>This happens in constant time</a>. #### Worst Case: O(n) Resizing the array requires an arraycopy() call, which is an <a href=https://stackoverflow.com/questions/7165594/time-complexity-of-system-arraycopy>O(n) algorithm</a>. ## boolean rotate(int n) ### LinkedList: O(n) I implemented this method recursively. You first need to define what a single rotation is, then traverse to the end of the list, then execute the rotation.The rotation itself takes constant time, however, traversing to the end of the list takes linear time. This will also scale linearly with the number of rotations you need to execute, however the problem scales linearly as rotations remain constant There is an optimization for both implementations, where you don't need to rotate n times, but rather n mod size() times. ### ArrayList: O(n) I implemented this the same way as I did LinkedList, however getting to the end of the list takes constant time (as above). I used a System.arraycopy() call, which scales linearly as the list increases in size. Once again, assuming constant rotations, the problem scales as arraycopy scales. ## void merge(List\<T\> other) ### LinkedList: O(n) Discarding sorting, you walk down both lists, inserting values where necessary. Because you already keep track of where to insert new nodes, this will execute until you are done inserting the nodes from other. This occurs when you have fully traversed other, hence an O(n) time complexity. ### ArrayList: O(n2) (Worst, possibly average case) Once again, the algorithm terminates as you finish traversing other. However, every time you need to insert a value, an arraycopy() call is made to make room for the new element. Hence as the arrays grow in size, the time required to execute scales quadratically.A best case scenario occurs when both arrays are sorted and there is no overlap in their elements (i.e. they can be mapped to finite subsets of disjoint intervals). In this case, the array will be traversed one time, and the algorithm will terminate. This will yeild an O(n) time complexity. ## void reverse() ### LinkedList: O(n) This algorithm works by walking down the array, and swapping the direction of the pointers. You only traverse the list one time, hence an O(1) algorithm. ### ArrayList: O(n) This algorithm works by walking to the midpoint of the array, and at each point, swapping the current element with one an equal distance (in the array) away. As the array grows, this algorithm will always grow with half of the array's length. Hence it grows linearly.