Question 3 Suppose the running times of an algorithm for inputs of size 1,000, 2,000, 3,000, and 4,000 are 5 seconds, 40 seconds, 135 seconds, and 320 seconds, respectively, and respond to the following.

Estimate how long it will take to solve a problem of size 5,000. Is the algorithm linear, linearithmic, quadratic, cubic, or exponential? Give an explanation of your answer.

Question 4 Each of the four Java functions given here returns a string of length n whose characters are all y. Determine the order of growth of the running time of each function. Recall that concatenating two strings in Java takes time proportional to the length of the resulting string.

Function 1. public static String method1(int n) { char[] temp = new char[n]; for (int i = 0; i < n; i++) temp[i] = 'y'; return new String(temp); }

Function 2. public static String method2(int n) { String s = ""; for (int i = 0; i < n; i++) s = s + "y"; return s; }

Function 3. public static String method3(int n) { if (n == 0) return ""; String temp = method1(n / 2); if (n % 2 == 0) return temp + temp; else return temp + temp + "y"; }

Function 4. public static String method4(int n) { if (n == 0) return ""; if (n == 1) return "y"; return method3(n/2) + method3(n - n/2); }