1) Learning Objective: To demonstrate the student can identify the key operation when finding the asymptotic time complexity of an algorithm. Instructions: This exercise is not graded, so you do not need to include your solution in your word processing document. Problem: Consider this split() method where: pList is an ArrayList of Integers containing zero or more elements; pEvenList is an empty ArrayList of Integers; and pOddList is an empty ArrayList of Integers. On return, pEvenList will contain the even Integers of pList and pOddList will contain the odd Integers. void split(ArrayList pList, ArrayList pEvenList, ArrayList pOddList) { for (int n : pList) { if (n % 2 == 0) pEvenList.add(n); else pOddList.add(n); } } To analyze the worst case time complexity of an algorithm we first identify the "key operation" and then derive a function which counts how many times the key operation is performed as a function of the size of the input. What is the key operation in this algorithm? Explain. Hint: One way to determine the key operation is to identify the operation which will be performed the most number of times during the execution of algorithm. Also, the key operation is generally an operation that is at the heart of the algorithm. For example, in the iterative linear search algorithm, the key operation is the comparison of pKey to the element in pList that is currently being examined because in order to find pKey we compare each element in pList to pKey. That comparison will be performed the most number of times during the execution of the algorithm and the entire point of the algorithm is to find the key, so comparing the current element to pKey is at the heart of the algorithm.

2) Learning Objective: To demonstrate that the student understands the definition of Big O. To demonstrate that the student understands how to derive the function f(n) which computes how many times the key operation of an algorithm is performed as a function of the size of the problem. Instructions: This exercise is graded, so include your solution in your word processing document. Problem: Continuing with the previous exercise, derive a function f(n) which equates to the number of times the key operation is performed as a function of n, where n is the size of pList. State the worst case time complexity of split() in Big O notation. You do not need to formally prove it but explain your answer.