The purpose of this assignment is to practice your analysis of algorithm complexity. In the second part of this assignment you will be asked to empirically test the performance of four different data structures for storing and searching. For each of the algorithms below:

1. State the size of the input in big-Oh. For example, if the input to an algorithm is an array of size k, then the input size is O(k). (1 mark)

2. Derive the cost function for the algorithm. Be sure to show your work like we do in lectures. You can use O(1) to denote all constants. (2 marks)

3. State the complexity of the algorithm in Big-Oh. The complexity MUST be stated in terms of input-size. (2 marks)

Example: Multiplication input: A[k] // A vector (10 array) of size k B[k] // A vector (10 array) of size k output: AB // A matrix of kxk in size R = array[k] [k] // new array of size k x k [O(1)] for j = 0 ...k for i = 0 ...k R[i][j] = A[j] * B[i] [k] [k] x [k] [k] x [k] x [0(1)] return R O(1) +k+k xk+k x k x 0(1) + O(1) = 0(1) + [0(1)] (k) = O(k) (k) + Solution 1. The inpput size is O(k) + (k) Ok) 2. f(k) = 0(1)+k x 0(1) + kx 0(1) 3. f(k) O(k) Problem: Last Resort? input: A[k] // 1D array of size k, k is a power of 2 output: sorted array A B = array(k) size = 1 while size