Top of Form Question 1 (1 point) Which of the following has an order of growth (

Question

Top of Form

Question 1 (1 point)

Which of the following has an order of growth (as a function of N) that is constant?

Question 1 options:

count++;

for (int i=1; i<N; i*=2)
    count++;

for (int i=1; i<N; i+=1)
    count++;

for (int i=1; i<N; i*=2)
    for (int j=1; j<N; j+=1)
      count++;

for (int i=1; i<N; i+=1)
    for (int j=1; j<N; j+=1)
      count++;

Question 2 (1 point)

Which of the following has an order of growth (as a function of N) that is logarithmic?

Question 2 options:

count++;

for (int i=1; i<N; i*=2)
    count++;

for (int i=1; i<N; i+=1)
    count++;

for (int i=1; i<N; i*=2)
    for (int j=1; j<N; j+=1)
      count++;

for (int i=1; i<N; i+=1)
    for (int j=1; j<N; j+=1)
      count++;

Question 3 (1 point)

Which of the following has an order of growth (as a function of N) that is linear?

Question 3 options:

count++;

for (int i=1; i<N; i*=2)
    count++;

for (int i=1; i<N; i+=1)
    count++;

for (int i=1; i<N; i*=2)
    for (int j=1; j<N; j+=1)
      count++;

for (int i=1; i<N; i+=1)
    for (int j=1; j<N; j+=1)
      count++;

Question 4 (1 point)

Which of the following has an order of growth (as a function of N) that is linearithmic?

Question 4 options:

count++;

for (int i=1; i<N; i*=2)
    count++;

for (int i=1; i<N; i+=1)
    count++;

for (int i=1; i<N; i*=2)
    for (int j=1; j<N; j+=1)
      count++;

for (int i=1; i<N; i+=1)
    for (int j=1; j<N; j+=1)
      count++;

Question 5 (1 point)

Which of the following has an order of growth (as a function of N) that is quadratic?

Question 5 options:

count++;

for (int i=1; i<N; i*=2)
    count++;

for (int i=1; i<N; i+=1)
    count++;

for (int i=1; i<N; i*=2)
    for (int j=1; j<N; j+=1)
      count++;

for (int i=1; i<N; i+=1)
    for (int j=1; j<N; j+=1)
      count++;

Question 6 (1 point)

Give the order of growth (as a function of N) of the running time of the following function.

    static long f (long N) {
        long sum = -1;
        while (N > 0) {
            N /= 2;
            sum++;
        }
        return sum;
    }

Question 6 options:

constant

logarithmic

linear

linearithmic

quadratic

cubic

exponential

Question 7 (1 point)

Give the order of growth (as a function of N) of the running time of the following function.

    static long f (long N) {
        long sum = 0;
        for (long i = 1; i < N; i *= 2)
            for (long j = 0; j < i; j++)
                sum++;
        return sum;
    }

Question 7 options:

constant

logarithmic

linear

linearithmic

quadratic

cubic

exponential

Question 8 (1 point)

Give the order of growth (as a function of N) of the running time of the following function.

    static long f (long N) {
        long sum = 0;
        for (long i = 1; i < N; i *= 2)
            for (long j = 0; j < N; j++)
                sum++;
        return sum;
    }

Question 8 options:

constant

logarithmic

linear

linearithmic

quadratic

cubic

exponential

Question 9 (1 point)

The following function returns a string of length N whose characters are all 'x'. Give the order of growth (as a function of N) of the running time.

Recall that concatenating two strings in Java takes time proportional to the sum of their lengths.

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

Question 9 options:

constant

logarithmic

linear

linearithmic

quadratic

cubic

exponential

Question 10 (1 point)

The following function returns a string of length N whose characters are all 'x'. Give the order of growth (as a function of N) of the running time.

Recall that concatenating two strings in Java takes time proportional to the sum of their lengths.

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

Question 10 options:

constant

logarithmic

linear

linearithmic

quadratic

cubic

exponential

Bottom of Form

count++;

for (int i=1; i<N; i*=2)
    count++;

for (int i=1; i<N; i+=1)
    count++;

for (int i=1; i<N; i*=2)
    for (int j=1; j<N; j+=1)
      count++;

for (int i=1; i<N; i+=1)
    for (int j=1; j<N; j+=1)
      count++;

Explanation / Answer

for (long i = 1; i < N; i *= 2)

            for (long j = 0; j < i; j++)

                sum++;

The first loop increments by twice. Hence it is logarithmic

The i runs like 1,2,4,8,16,32,

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.