Compare sorting algorithms by counting their work
Three steps, the way the exam actually works: work through the lab, write down your own measurements, then answer a 6-point free response. What you recorded goes to the grader with your writing, so a conclusion that does not follow from your own numbers will cost you the point — exactly as it would with a real reader.
Predict before you look
- Bubble sort compares neighboring pairs repeatedly; merge sort splits the array and merges sorted halves. Which do you expect to scale worse as n grows, and why?
- If an algorithm is O(n²), what factor does its work grow by when you double n? Answer with a number.
Nothing to submit here — these are to think through, so the prediction below is an informed one rather than a guess.
Commit to an answer now. It is not graded and being wrong costs nothing — the point is to have something specific to reconcile against once you have the data.
Answer every prediction to unlock the lab. A sentence is enough.
Run the investigation
Predictions first
The procedure and the simulation unlock once you have committed above. Observing before predicting is how a wrong intuition survives a lab intact.
Record what you measured
These are your numbers, not ours. The grader sees them, so your conclusions have to follow from what you actually recorded.
| Bubble sort comparisons at n = 14 | |
|---|---|
| Merge sort comparisons at n = 14 | |
| The larger array size you used | |
| Bubble sort comparisons at that larger size | |
| Binary search comparisons |
Answer the free response
You measured the work each algorithm actually performs. (a) Compare your two comparison counts at n = 14 and state which algorithm did less work. Give the Big-O complexity of each and explain what that notation describes. (b) Using your two bubble-sort measurements at different array sizes, show that the growth is consistent with a quadratic rather than a linear cost. Support this with the ratio of your counts. (c) Explain why merge sort achieves O(n log n) by describing what the algorithm does at each level of recursion and how many levels there are. (d) Your binary search finished in very few comparisons. State its complexity, and identify the precondition that must hold before it can be used at all.
Sign in to have this graded and saved to your progress.