7.9. Hard Multiple Choice QuestionsΒΆ

These problems are harder than most of those that you will usually see on the AP CS A exam.

This problem is about big O notation which is not covered on the A exam. It used to be covered on the AB exam, but they stopped offering that exam several years ago.

    6-9-1: Which best characterizes the running time of the following code segment?

    for (int j = 1; j <= n; j++) {
       for (int k = 1; k <= n; k = k * 2)
          System.out.println(j + " " + k);
    }
    
  • O(log n)
  • This would be correct if there was just the inner loop.
  • O(n log n)
  • The outer loop is n but the inner loop is log n since k is multiplied by 2 each time through the loop.
  • O(n)
  • This would be correct if there was just the outer loop.
  • O(n*n)
  • This would be correct if the inner lop was incremented by 1 instead of multiplied by 2.
  • O(n!)
  • To get n! as big-oh we would need n nested loops.
Next Section - 7.10. Free Response - Self Divisor A