# 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.

- (A) O(log n)
- This would be correct if there was just the inner loop.
- (B) 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.
- (C) O(n)
- This would be correct if there was just the outer loop.
- (D) O(n*n)
- This would be correct if the inner lop was incremented by 1 instead of multiplied by 2.
- (E) O(n!)
- To get n! as big-oh we would need n nested loops.

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);
}
```