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) n2
(b) n
(c) 2n
(d) 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



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

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

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



3.

Consider the following code fragment.

      for( int i = n; i > 0; i /= 2 ) body;

If body executes in O(1) time, then the asymptotic running time of the code fragment above 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



4.

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(n)
(b) O(n2)
(c) O(log n)
(d) O(n log n)

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



5.

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(n log n)
(b) O(log n)
(c) O(n2)
(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



6.
Using the standard gradeschool method, what is the asymptotic running time of multiplying two numbers that are both n digits long?

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

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



7.
Using the standard gradeschool method, what is the asymptotic running time of adding two numbers that are both n digits long?

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

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.
What is the asymptotic running time of merge sort with an input array of length n?

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

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 += 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(n log n)
(b) O(n2)
(c) O(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



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 log n)
(b) O(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: 100.00