5. What is the Big-O running time of the following code fragment? public static

Question

 5.  What is the Big-O running time of the following code fragment?         public static int calc( List<Integer> lst )       {          int count = 0;          int N = lst.size();           for ( int i=0; i<N; i++)          {             if (lst.get(i) > 0)                sum += lst.get(i);             else                sum += lst.get(i) * lst.get(i);          }          return sum;       }       a.  If an ArrayList is passed for lst.  Explain your answer.    b.  If a LinkedList is passed for lst.  Explain your answer.  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-O running time if:    a.  If an ArrayList is passed.  Explain your answer.    b.  If a LinkedList is passed.  Explain your answer. 

Explanation / Answer

5. a) If arraylist has been passed, then the operation lst.get(i) is O(1), hence total running time becomes O(N)
b) If Linkedlist is passed for lst, then lst.get(i) is a O(N) operation, because linked lists are sequential lists and don't llow random access.. Hence the overall runnning time will be O(N^2)

6. Assuming stack push and pop operations are O(1)
1) For ArrayList, The removal of elements is O(N) for each element, hence O(N^2) for removal and for pushing to stack.. Now if do N operations to retrieve values from stack and push on the arraylist.. SO it is now a O(N) operation because we need to put at the end only, and it being random access, will take O(N).. Hence The overall complexity remains O(N^2)

2) For linked list, the elements are pushed one by one on the stack... We can traverse all elements at one go in O(N) time and remove them, also they will also be pushed to stack in this time.. Now Again, we get them one by one and we need to insert each new item at the back of the list.. Hence now it being linked list, doesn;t allow random position access.. Hence the second step will take O(N^2). hence overall complexity is O(N^2)

Related Questions

Navigate

• Browse (All)
• Browse 5
• Subjects

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