1. (6 points) A. What is the complexity (big-O) of the following code fragment? for (i = 0; (i < n) || (i < m); i++) { sequence of statements } B. We have the following recursive function. Assume you call: something(0, n); find the complexity in terms of n. void something(int b, int e) { if (b >= e) return; int a = 0; for(int i=b; i < e; i++) a++; int k = (b+e)/2; something(b, k); something(k+1, e); } 2. (10 points) Consider this tree and answer these questions: a. Which nodes have degree 2? b. What is the depth of M? c. What is the height of M? d. Which nodes are leaf nodes? e. What is the pre order traversal of the tree? 3. (6 points) a. Is the following array a binary heap? [10, 3, 5, 1, 4, 2] (explain it) b. Draw a max-heap on the following set of integers: {2, 3, 5, 7, 11, 13, 17} (you do not need to use Build-heap algorithm) 4. (6 points) Compare the following sorts in terms of time and space complexity. - Quicksort - Mergesort - Heapsort 5. (4 points) What is the definition of perfect binary tree? What is the definition of complete binary tree? 6. (8 points) Assume you have a hash-table of size 7 and you want to insert these items (in the given order) into the hash-table (using double hashing). Show that how many probes are required to insert these items (in the given order): 51, 40, 69, 5, 55 7. (10 points) Write a code for merging two sorted arrays (L1 and L2). This is the signature of the method: (the result should be stored in array res) void merge(Comparable[] res, Comparable[] L1, Comparable[] L2); What is the time complexity?