1)What is the Big-O running time of the following code fragment? Assume lst1 has
ID: 3542288 • 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? 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? 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.
Explanation / Answer
If a LinkedList is passed. (get operations are O(N) for LinkedList)
O(N^4)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.