NAME:

LOGIN:

PRECEPT:

COS 226 Exercises on Analysis of Algorithms


Each of the four Java functions below returns a string of length N whose characters are all x. Determine the order of growth of the running time of each function, e.g., log N, N, N log N, N^2, N^3, or 2^N. Give a brief explanation. Recall that concatenating two strings in Java takes time proportional to the sum of their lengths.


1. 

 public static String method1(int N) {
     String s = "";
     for (int i = 0; i < N; i++)
         s = s + "x";
     return s;
 }












2. 
 public static String method2(int N) {
    if (N == 0) return "";
    if (N == 1) return "x";
    return method2(N/2) + method2(N - N/2);
 }












3. 
 public static String method3(int N) {
    char[] temp = new char[N];
    for (int i = 0; i < N; i++)
        temp[i] = 'x';
    return new String(temp);
 }