Question 1 ========== We'll need to count the integers from x to y for integers x and y. For x <= y: [x,y) contains y-x integers, (x,y] contains y-x integers, [x,y] contains y-x+1 integers. A - Since a = 0 or a >=1: a <= a^2. 1st loop executes m once for each integer in [a,a^2): a^2-a times. 2nd loop starts with j-i = a >= 0, then ++i and --j decrease j-i by 2, while j-i >= 0. So it executes m for each of a, a-2, a-4, ..., 1 or 0. Case a even: a = 2k for some k; 2k, 2(k-1), ..., 2(0) = k+1 times. Case a odd: a = 2k+1 for some k; 2k+1, 2(k-1)+1, ..., 2(0)+1 = k+1 times. Grand total a even: a^2-a + a/2 + 1 = a^2 - a/2 + 1 times. a odd: a^2-a + (a+1)/2 = a^2 - (a-1)/2 times. [Test this the way you test code: try extreme/boundary cases and typical cases. Since we also cared about even vs odd, a good set of tests would be: a = 0, 2, 10 a = 1, 3, 9] B - Method m1 executes m for each integer in [0,a^2] = a^2+1 times, where a is the value of the parameter. The call to m1 sets the parameter to a^2, so number of calls to m: (a^2)^2 + 1 = a^4 + 1. C - For a = 0 the k loop doesn't execute m. For a >= 1 it executes m for each integer in [1,a) = a-1 times. The j loop executes the k loop for Case a even: integers in (0,a/2] = a/2 times. Case a odd: integers in (0,(a-1)/2] = (a-1)/2 times. So the j loop executes m Case a = 0: 0 times. Case a even, a != 0: (a-1)*a/2 times. Case a odd: (a-1)/2 * (a-1) = (a-1)^2 / 2 times. The i loop executes the j loop for each of: Case b even: once for each of a, a+2, ..., a+b-2 = once for each of 0, 2, ..., b-2 = once for each of 0, 1, ..., (b-2)/2 = b/2 times. Case b odd: a+2k always != a+b, so infinite loop. Grand total: b odd: a = 0 or 1: 0 times (but infinite loop!) a >= 2: infinite number of times. b even: a even: b/2 * (a-1) * a/2 = ba(a-1) / 4 times. a odd: b/2 * (a-1)^2 / 2 = b(a-1)^2 / 4 times. D - The j loop executes m Case i >= 148: i - 148 times. Case i < 148: 0 times. The i loop executes the j loop for each i in [0,a). Case a < 149: i < 148, so j loop never executes m, so m executed 0 times. Case a >= 149: j loop doesn't execute m for each i < 148, then (148-148) + (149-148) + ... + (a-1 - 148) times = 0 + 1 + 2 + ... + a-149 times = (a-149) * (a-149 + 1) / 2 = (a-149) * (a-148) / 2 times. Question 2 ========== We do part B first, since it helps us understand part A. Also, a few quick checks show that our answers work even if one or both pieces are empty. Part B ------ The code keeps copying the smallest element not copied, by taking the smallest uncopied element of each piece and copying the smaller of those two. For ties, it uses the 2nd piece. It stops when: 1st piece completely copied remaining elements of 2nd piece are the ones > last/all element/elements of 1st piece so copied elements of 2nd piece are the ones <= last/some element of 1st piece [A65/165 people: notice negation of universal turning into existence of negation] OR 2nd piece completely copied remaining elements of 1st piece are the ones >= last/all element/elements of 2nd piece so copied elements of 1st piece are the ones < last/some element of 2nd piece So: If last element of 1st piece < some element of 2nd piece number of iterations = length of 1st piece + number of elements in 2nd piece <= last element of 1st piece Else number of iterations = length of 2nd piece + number of elements in 1st piece < last element of 2nd piece Part A ------ Loop ends with i0 = i or i1 = p.length. Elements of p[0..i0) and p[i..i1) were copied to temp[0..t) in nondecreasing order. Case i0 = i: p[0..i1) copied to temp[0..t) in nondecreasing order, and t = i1. Uncopied elements of p are at end of p, where they should be! Just copy temp[0..t) to p[0..t). Case i1 = p.length: Remaining uncopied elements: p[i0..i). Copy them to end of p (from t onward, since t elements were copied). Then copy temp[0..t) to p[0..t). Code: if (i1 == p.length) { System.arraycopy(p, i0, p, t, i - i0); } System.arraycopy(temp, 0, p, 0, t); If you are at all unsure of your logic or Java, you of course tested it. Question 3 ========== Q3 q [x0] [x0 | Q3 q[null] int i[0] ] --- --- Q3 q [x0] [x0 | Q3 q[ x1 ] int i[0] ] [x1 | Q3 q[null] int i[1] ] --- Q3 q [x0] [x0 | Q3 q[ x1 ] int i[0] ] [x1 | Q3 q[ x2 ] int i[1] ] [x2 | Q3 q[null] int i[2] ] --- Q3 q [x0] [x0 | Q3 q[ x1 ] int i[0] ] [x1 | Q3 q[ x2 ] int i[1] ] [x2 | Q3 q[ x3 ] int i[2] ] [x3 | Q3 q[null] int i[3] ] --- --- Q3 q [x0] [x0 | Q3 q[ x1 ] int i[0] ] Q3 c [x0] [x1 | Q3 q[ x2 ] int i[1] ] [x2 | Q3 q[ x3 ] int i[2] ] [x3 | Q3 q[null] int i[3] ] --- Q3 q [x0] [x0 | Q3 q[ x1 ] int i[0] ] Q3 c [x1] [x1 | Q3 q[ x2 ] int i[1] ] [x2 | Q3 q[ x3 ] int i[2] ] [x3 | Q3 q[null] int i[3] ] --- --- Q3 q [x0] [x0 | Q3 q[ x1 ] int i[0] ] Q3 c [x1] [x1 | Q3 q[ x2 ] int i[1] ] Q3 d [x4] [x2 | Q3 q[ x3 ] int i[2] ] [x3 | Q3 q[null] int i[3] ] [x4 | Q3 q[null] int i[4] ] --- --- Q3 q [x0] [x0 | Q3 q[ x1 ] int i[0] ] Q3 c [x1] [x1 | Q3 q[ x2 ] int i[1] ] Q3 d [x4] [x2 | Q3 q[ x3 ] int i[2] ] [x3 | Q3 q[null] int i[3] ] [x4 | Q3 q[ x2 ] int i[4] ] --- Q3 q [x0] [x0 | Q3 q[ x1 ] int i[0] ] Q3 c [x1] [x1 | Q3 q[ x4 ] int i[1] ] Q3 d [x4] [x2 | Q3 q[ x3 ] int i[2] ] [x3 | Q3 q[null] int i[3] ] [x4 | Q3 q[ x2 ] int i[4] ] --- --- Q3 q [x1] [x0 | Q3 q[ x1 ] int i[0] ] Q3 c [x1] [x1 | Q3 q[ x4 ] int i[1] ] Q3 d [x4] [x2 | Q3 q[ x3 ] int i[2] ] [x3 | Q3 q[null] int i[3] ] [x4 | Q3 q[ x2 ] int i[4] ]