### COS 226 Exercises on Analysis of Algorithms

Reference: Section 1.4 in Algorithms, 4th edition

1. The two Java functions below each return a string of length N whose characters are all x. Determine the order of growth of the running time of each, e.g., log N, N, N log N, N^2, N^3, or 2^N. Give a brief explanation.

```    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;
}
```
Hint: Recall that concatenating two strings in Java takes time proportional to the sum of their lengths.

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.

1. Given an integer x and a sorted array a[] of N distinct integers, design a linear-time algorithm to find if there exists indices i and j such that (a[i] + a[j] == x).

Hint: start by checking whether a[0] + a[N-1] is smaller than, greater than, or equal to x.

2. Given an array a[] of N distinct integers, design a quadratic-time algorithm to find if there exists indices i, j, and k such that (a[i] + a[j] + a[k] == 0).

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.