1. reverse List, shown below, places items in the first list (of the size N) int

Question

1. reverse List, shown below, places items in the first list (of the size N) into the second list in reverse order. public void reverseList List original, List reverse reverse clear(); for( int i e; i original size( )i i++) reverse add(e, original, get(i) (a) What is the running time of reverseList when both lists are Arraylusts? o(NA2) because the calls to add are o (N) each (b) What is the running time of reverseList when both lists are LinkedLists? o( NA2) because the calls to get are o(N) each is a (c) What is the running time of reverseList when original is an ArrayList and reverse LinkedList? both o(1) each o(N) because the calls to add and get are long (d) suppose it takes 10 seconds to run reverseList on two 1000-item ArrayLists. How will it take to run reverseList on two ArrayLists? a algorithm, when N is increased by a factor of 3, the running time increases by a factor So the time will sec. Note: Justify your answers.

Explanation / Answer

a. See when both are array List

Lets say you have two list orignal and Reverse : Orignal contains 1 2 3 4 5

Now , we loop through Original List and add elements at the front

1
2 1
3 2 1
4 3 2 1
5 4 3 2 1
Will be our reverse list at the end of Loop

Time Complexity :

When we add an element to array list it takes O(N) , why because lets say we
had 3 2 1 already in the list and we want to add 4 so that it becomes 4 3 2 1
In place of 3 we need to add 4 and in place of 2 element 3 will come basically we have to shift all the elements by one , So we will go till thge end of arraylist and shift by one..So for adding a single element we ytraversed the whole list

So for adding N elements it will take NXN = N2 , Remember it was array based list so we had to shift all elements by one.


b) When both are Linked List

Lets say you have two list orignal and Reverse : Orignal contains 1 2 3 4 5

Now , we loop through Original List and add elements at the front

1
2 1
3 2 1
4 3 2 1
5 4 3 2 1

Will be our reverse list at the end of Loop

Time Complexity :

When we add an element to array list it takes O(1) ,because we just have to attach node to front

But to get the element from LinkedList it takes us O(N) everytime. Lets see why
Suppose we have 1 2 3 4 5 already in the Linked list and we want to add 4 so that my reverse list becomes 4 3 2 1.
We need to get(4th element) , So we traverse from beginning to end because LinkedList are not stored based on index unlike array list, So for any element we need to traverse. For ith element it takes ith time


So for adding N elements it will take 1 + 2 +3 +4 ..N time = O(N2) because get was taking ith time for ith list
and we know that sum of series from 1 to N is N2
Remember it was Linked based list so adding an element was O(1) because just attach pointers using next


c) Orignal is ArrayList, reverse is Linkedlist

Lets say you have two list orignal and Reverse : Orignal contains 1 2 3 4 5

Now , we loop through Original List and add elements at the front

1
2 1
3 2 1
4 3 2 1
5 4 3 2 1

Time complexity
Will be our reverse list at the end of Loop

As we know adding an element in Linked list takes O(1), So outer loop will run N times and adding will take O(1) .
Total time complexity is O(N) as we dont have to shift because reverse one is linked list


Thanks, let me know if there is any doubts

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.