Algorithmic Efficiency FRQ Practice

Responses receive AI feedback against a rubric after submission. Scores are practice estimates.

Question 1 of 5

A sorted list has 10 items. (a) Worst-case checks for a full linear scan? (b) Binary search halves: start 10, then about 5, then 3, then 2, then 1 (count these stages). (c) Which approach uses fewer checks in this sketch?

Question 2 of 5

Algo A: 5n steps. Algo B: n^2 steps. (a) Evaluate both at n = 6. (b) Evaluate both at n = 11. (c) State which is larger at n = 11 and justify with arithmetic.

Question 3 of 5

A password cracker tries every length-n string over 2 symbols (2^n trials). (a) How many trials for n = 4? (b) How many for n = 8? (c) Explain why this is considered unreasonable growth for large n compared with a 2n-trial method.

Question 4 of 5

A navigation app needs a route quickly during rush hour. Computing a guaranteed shortest path among huge maps takes too many steps. (a) Why might a heuristic be used? (b) What does it mean that a heuristic is not guaranteed optimal? (c) Give one example of a step-count comparison you would want between the exact and heuristic methods for a sample map size.

Question 5 of 5

Algorithm CountMax scans n scores once to find a maximum (n comparisons after the first value). (a) For n = 12, how many comparisons after reading the first score? (b) If a second algorithm rescans the list 12 full times (12n comparisons), compute its comparisons for n = 12. (c) Which is more efficient on this input size by step count?