1. What is the Big-O running time of the following code fragment? Assume lst1 ha
ID: 3550014 • Letter: 1
Question
1. What is the Big-O running time of the following code fragment? Assume lst1 has N items, and lst2 is initially empty. public static void add( List<Integer> lst1, List<Integer> lst2) { for ( Integer x : lst1 ) lst2.add(0, x); // add to front } a. If an ArrayList is passed for lst1 and lst2. Explain your answer. b. If a LinkedList is passed for lst1 and lst2. Explain your answer. 2. What is the Big-O running time of the following code fragment? Assume lst has N items. public static void erase( List<Integer> lst ) { Iterator<Integer> itr = lst.iterator(); while ( itr.hasNext() ) { Integer x = itr.next(); itr.remove(); } } a. If an ArrayList is passed for lst. Explain your answer. b. If a LinkedList is passed for lst. Explain your answer. 3. What is the Big-O running time of the following code fragment? Assume lst1 has N items, and lst2 has M items. public static int Count( List<Integer> lst1, List<Integer> lst2) { Iterator<Integer> itr1 = lst1.iterator(); int count=0; while ( itr1.hasNext() ) { Integer x = itr1.next(); Iterator<Integer> itr2 = lst2.iterator(); while ( itr2.hasNext() ) if ( x.equals( itr2.next()) ) count++; } return count; } a. If an ArrayList is passed for lst1 and lst2. Explain your answer. b. If a LinkedList is passed for lst1 and lst2. Explain your answer. 4. What is the Big-O running time of the following code fragment? Assume lst has N items. 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. Explain your answer. b. If a LinkedList is passed. Explain your answer.
Explanation / Answer
1)
The for loop iterates for N times.
a) Linked List : Adding an element in the front of a linked list is O(1). Therefore total time complexity is O(N).
b) Array : Adding an element in the front of an array when list2 contains "i" elements is O(i)
Therefore total time is O(1) + O(2) + ... O(i) + .... O(N-1) = O(N^2).
2)
The while loop iterates for N times.
a) Linked List : Removing an element from a linked list is O(1). Therefore total time complexity is O(N).
b) Array : Removing an element at ith position of an array when is O(N-i)
Therefore total time is O(N-1) + O(N-2) + ... O(N-i) + .... O(1) = O(N^2).
3)
Traversing the list for an array and Linked list takes the same time O(N) for a list of size N.
The first loop for list1 iterates for O(M) times and loop for list2 iterates for O(N) times. And for every iteration for loop1, loop2 iterates N times.
Therefore taotal times complexity for array list and linked list is the same and is equal to O(MN).
4)
The for loop iterates N times.
Array : Time complexity to get ith item is O(1) .Therefore total time complexity for Array is O(N).
Linked List : Time complexity to get ith item of Linked list is O(i).
Therefore total time complexity is O(1) + O(2) .... + O(i) +.... O(N-1) = O(N^2).
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.