This book is now obsolete Please use CSAwesome instead.

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.
You have attempted of activities on this page