12.4. Preview Questions#
Complete these questions before class to prepare for the chapter. Use the dropdowns to check your answers.
12.4.1. True or False#
1. Binary search requires the array to be sorted.
Answer
True — Binary search relies on the sorted order to eliminate half the elements each step.
2. Linear search has O(log n) time complexity.
Answer
False — Linear search checks every element in the worst case — O(n).
3. Bubble sort is one of the most efficient algorithms for large datasets.
Answer
False — Bubble sort is O(n²) — very slow for large inputs.
4. Big-O notation describes how an algorithm’s runtime scales with input size.
Answer
True — Big-O characterizes growth rate, not exact runtime.
5. Merge sort has O(n log n) average time complexity.
Answer
True — Merge sort consistently runs in O(n log n) time.
12.4.2. Multiple Choice#
1. What is the time complexity of binary search?
a) O(n)
b) O(n²)
c) O(log n)
d) O(1)
Answer
c) O(log n) — Each comparison halves the search space, giving O(log n).
2. Which sorting algorithm repeatedly swaps adjacent elements if out of order?
a) Merge sort
b) Quick sort
c) Insertion sort
d) Bubble sort
Answer
d) Bubble sort — Bubble sort bubbles the largest unsorted value to its position each pass.
3. An O(1) algorithm means:
a) It takes exactly one second
b) Its runtime grows linearly
c) Its runtime is constant regardless of input size
d) It contains exactly one loop
Answer
c) Its runtime is constant regardless of input size — Constant time means performance does not depend on input size.
4. Which algorithm recursively divides the array in half and merges results?
a) Bubble sort
b) Linear search
c) Merge sort
d) Selection sort
Answer
c) Merge sort — Merge sort uses divide-and-conquer: split, sort halves, then merge.
5. If an algorithm is O(n²), doubling the input size roughly:
a) Doubles the runtime
b) Has no effect
c) Quadruples the runtime
d) Halves the runtime
Answer
c) Quadruples the runtime — (2n)² = 4n² — quadruple growth for doubled input.
Footnotes