Big O Notation Quiz

Example Questions From the Test

• 1A recursive binary search passes only array indices and creates one recursive call at each level. What is its auxiliary call-stack space complexity?
  • O(n), because the original array contains n elements.
  • O(1), because each individual stack frame has constant size.
  • O(log n), because one frame is added at each level while the search range is repeatedly halved.
  • O(n log n), because the array size is combined with the recursion depth.
• 2An algorithm performs 4n² + 3n + 20 basic operations. What is its tight asymptotic running time?
  • Quadratic time, because the n² term dominates as n grows.
  • Linear time, because lower-order terms and constants are removed.
  • Logarithmic time, because only the number of input-size digits matters.
  • Cubic time, because the expression contains three separate terms.
• 3If an algorithm takes Θ(n²) time, approximately how does its work change when n is doubled for large n?
  • It becomes about four times as large.
  • It becomes about twice as large.
  • It becomes about eight times as large.
  • It remains approximately unchanged.