Question

6. Suppose a Java method receives a List<Integer> and reverses the order of the items it contains by removing each item from the front of the list and pushing it onto a Stack<Integer), and then popping the items from the stack and inserting each item to the end of the list. What is the expected Big- running time if: a. If an ArrayList is passed. Explain your answer. b. If a LinkedList is passed. Explain your answer.

Please explain clearly. Thank you for your time and help will upvote!

Answer 1

Operations needs to do when you want to reverse list are
1. Removing item from front of the list
2. Pushing it to stack
3. popping items from stack
4. Inserting each item to the end of the list

Stack operations are done at time complexity of O(1)

List operations from above are
1. Removing item from front of the list
2. Inserting each item to the end of the list

=====================================

a) When ArrayList is passed
1. Removing item from front of the list
Time complexity to do this is O(n)
Because when we want to remove front element then we need to shift all the items in the list to left
 
2. Inserting each item to the end of the list
Time complexity = O(1)
Because we just need to put an item at end and increment size by 1

So, Total time complexity for 4 operations are = O(n) + O(1) + O(1) + + O(1) = O(n)

=====================================

b) When LinkedList is passed
1. Removing item from front of the list
Time complexity to do this is O(1)
Because when just need to move front to its next 
 
2. Inserting each item to the end of the list
Time complexity = O(n)
Because we need traverse from front to end and then we remove the link of the last item

So, Total time complexity for 4 operations are = O(1) + O(n) + O(1) + + O(1) = O(n)