Objective & prerequisites
Compare algorithm growth without confusing measurements with guarantees. Before starting: basic Python functions, dictionaries, loops, JSON and terminal use. Complete the earlier Git/API/testing workshops if these are unfamiliar. Download and extract the kit into a new practice folder, then open a terminal in the software-kit folder. Python 3.10+ is required; the reference uses only the standard library. Work with the supplied fictional data. These free companion lessons do not change protected course access or award progress or certificates.
python3 --version
python3 -m unittest discover -s tests -vUnderstand the concept
Complexity describes how work or storage grows with input size under stated assumptions. Scanning a growing list to detect every duplicate in an all-unique sequence performs 0+1+...+(n-1) comparisons: n(n-1)/2, which is quadratic growth. A set-based approach makes n membership calls and uses additional storage. Typical hash-table membership has expected constant-time behavior under normal assumptions, but this lesson does not promise a fixed worst-case time. Sorting usually changes the tradeoff to O(n log n), while a streaming running sum can be O(n) work with constant aggregate storage if uniqueness is checked elsewhere.
Worked example
comparison_counts(10) gives 45 list comparisons and 10 set membership calls. At 100 it gives 4950 and 100. A tenfold input increases the counted scan comparisons by 110 times in these two finite fixtures. As n grows, quadratic scaling tends toward a hundredfold work increase for tenfold n. These counts are not seconds, CPU instructions or evidence that the set operation itself has zero cost.
from dch_orders import comparison_counts
assert comparison_counts(20) == {"list_comparisons": 190, "set_membership_calls": 20}
print(comparison_counts(200))Try it yourself
Predict counts for n=0,1,20,200 and confirm them with comparison_counts. Calculate the list formula by hand for n=20. Explain why timing one tiny run is poor evidence of a general scaling law. Identify the O(n) storage used by the set and seen list. Write your expected outcome before running your implementation. Keep the supplied solution unchanged so that you can compare your own reasoning with it.
Worked solution
For n=0 the counts are 0 and 0; n=1 gives 0 and 1; n=20 gives 190 and 20; n=200 gives 19900 and 200. Both implementations retain an index growing with n. The helper bounds n at 1000 to avoid turning a teaching comparison into an accidental expensive run. The supplied tests assert independent known counts rather than elapsed-time thresholds.
Knowledge check
Does observing 100 membership calls prove the program takes exactly 100 units of time?
Check and explain
No. A call count describes an instrumented operation, not its hardware cost. State the operation, assumptions, memory tradeoff and tested input range.
Evidence & common mistakes
Record the exact command, Python version, observed output and one rejected input. Explain what each check establishes and what it leaves untested. Do not remove validation merely to obtain a passing result. A local passing suite is evidence for these fixtures, not proof of production readiness. Credit the teaching reference and distinguish your own changes. The kit includes an exercise worksheet, a separate worked-solutions document, an API contract, expected results and a capstone rubric.
Authoritative reference
— official reference for the underlying interface. Lesson prose and fictional order examples are original. The teaching HTTP service is loopback-only, stateless and not suitable for production or uploading as a running Aruba service. No cloud account, paid API or registration is required.
Try the activity before reading its reference. Keep your sources, commands and assumptions with your work. Companion activities are unsaved self-practice and do not award a certificate or change lesson progress.