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); }