View Assessment Result: Multiple Choice Quiz 7



Your performance was as follows:

1.
What is the asymptotic running time of insertion sort on an input array with length n?

(a) n
(b) n log n
(c) 2n
(d) n2

Correct answer is (d)

Your score on this question is: 10.00

Feedback:
   See section 1.7.1 of the course notes.
   (d) No Feedback



2.
Which of the following statements about insertion sort is true asymptotically?

(a) Insertion sort is slower than merge sort, and consumes more memory.
(b) Insertion sort is slower than merge sort, and consumes about the same memory.
(c) Insertion sort is slower than merge sort, but consumes less memory.
(d) Insertion sort is faster than merge sort, but consumes less memory.

Correct answer is (c)

Your score on this question is: 10.00

Feedback:
   See section 1.7.1 of the course notes.
   (c) No Feedback



3.

Consider the following code fragment.

      for( int i = 1; i < n; i *= 2 ) body;

If body executes in O(1) time, then the asymptotic running time of the code fragment above is



(a) O(n2)
(b) O(n log n)
(c) O(log n)
(d) O(n)

Correct answer is (c)

Your score on this question is: 0.00

Feedback:
   See section 1.7.1 of the course notes.
   (d) No Feedback



4.

Consider the following recursive definition of a function f.

int  f(int  n)
{
  if( n == 0 ) return 1;
  else return  f(n / 2);
}

The asymptotic running time of the call f(n) is



(a) O(log n)
(b) O(n2)
(c) O(n log n)
(d) O(n)

Correct answer is (a)

Your score on this question is: 10.00

Feedback:
   See section 1.7.1 of the course notes.
   (a) No Feedback



5.

Consider the following recursive definition of a function f.

int  f(int  n)
{
  if (n == 0) return 1;
  else return  f(n >> 1);
}

The asymptotic running time of the call f(n) is



(a) O(n)
(b) O(n log n)
(c) O(log n)
(d) O(n2)

Correct answer is (c)

Your score on this question is: 10.00

Feedback:
   See section 1.7.1 of the course notes.
   (c) No Feedback



6.

Consider the following definition of a recursive function, power, that will perform exponentiation.

      int  power( int b, int e )
      {
        if( e == 0 ) return 1;
        if( e % 2 = 0 ) return  power( b * b, e/2 ); 
        return  b * power( b * b, e/2 );
      }

Asymptotically in terms of the exponent e, the number of calls to power that occur as a result of the call power(b,e) is



(a) linear
(b) exponential
(c) quadratic
(d) logarithmic

Correct answer is (d)

Your score on this question is: 10.00

Feedback:
   See section 1.7.1 of the course notes.
   (d) No Feedback



7.

Consider the following code fragment.

      for( int i = 0; i < n; i++ )
            for( int j = 0; j < n; j++ )
                  for( int k = 0; k < n; k++ ) body;

If body executes in O(1) time, then the asymptotic running time of this code fragment is



(a) O(n2)
(b) O(n3)
(c) O(2n)
(d) O(n)

Correct answer is (b)

Your score on this question is: 10.00

Feedback:
   See section 1.7.1 of the course notes.
   (b) No Feedback



8.

Consider the following code fragment.

    for( int i = 0; i < n; i += 2 )
            for( int j = 0; j < n; j += 3 )
                  for( int k = 0; k < n; k += 4 ) body;

If body executes in O(1) time, then the asymptotic running time of this code fragment is



(a) O(n2)
(b) O(n)
(c) O(n log n)
(d) O(n3)

Correct answer is (d)

Your score on this question is: 10.00

Feedback:
   See section 1.7.1 of the course notes.
   (d) No Feedback



9.

Consider the following code fragment.

    for( int i = 0; i < n; i++ )
            for( int j = 0; j < n/5; j++ ) body;

If body executes in O(1) time, then the asymptotic running time of this code fragment is



(a) O(n2)
(b) O(n3)
(c) O(n)
(d) O(n log n)

Correct answer is (a)

Your score on this question is: 10.00

Feedback:
   See section 1.7.1 of the course notes.
   (a) No Feedback



10.

Consider the following code fragment.

for( int i = 0; i < n; i += 2 )
  for(int  j = i; j > 0; j -= 3 ) body

If body executes in O(1) time, then the asymptotic running time of this code fragment is



(a) O(n)
(b) O(n log n)
(c) O(n2)
(d) O(n3)

Correct answer is (c)

Your score on this question is: 10.00

Feedback:
   See section 1.7.1 of the course notes.
   (c) No Feedback



Go to top of assessment.

Total score: 90.00