1. What is the Big-O running time of the following code fragment? Assume lst1 ha
ID: 3790764 • 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. 16 points 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. 16 points 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. 16 points 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 sum = 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. 16 points 5. 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, pushing each item onto a Stack<Integer>, and then popping the items from the stack and inserting each item at the end of the list. Assume push and pop are O(1). 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. 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. 16 points 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. 16 points 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. 16 points 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 sum = 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. 16 points 5. 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, pushing each item onto a Stack<Integer>, and then popping the items from the stack and inserting each item at the end of the list. Assume push and pop are O(1). 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
int sum(int* data, int N) { int result = 0; // 1 for (int i = 0; iRelated Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.