Hint: Recall that concatenating two strings in Java takes time proportional to the sum of their lengths.public static String method1(int N) { String s = ""; String x = "x"; for (int i = 0; i < N; i++) s = s + x; return s; } public static String method2(int N) { String s = ""; String x = "x"; while (N != 0) { if (N % 2 == 1) s = s + x; x = x + x; N = N/2; } return s; }
2.
In this exercise, you will develop a quadratic-time algorithm for the 3-sum problem.
When we ask you to design an algorithm, give a crisp and concise
English description of your algorithm - don't write Java code.
Hint: start by checking whether a[0] + a[N-1] is smaller than, greater than, or equal to x.
Hint: Use the result from (a). You can assume the array is sorted since sorting the array can be done in quadratic (and even linearithmic) time.