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.