# 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