Choose what to remember and what work remains
| Value choice | Can answer | Does not retain |
|---|---|---|
| True | Has this date appeared? | Count and student identities |
| Count | How many records have this date? | Individual IDs |
| ID list | Which ID occurrences appeared? | Direct key membership without searching the list |
| ID dictionary | Which distinct IDs appeared? | Repeated copies of the same ID |
Under the course’s constant-time dictionary-operation assumption, a birthday presence/count scan does one small amount of dictionary work per record. Finding all pairs inside a large equal-date group still requires work for every pair output. Storing ID lists also needs space for those IDs. Do not claim the entire task, including arbitrary list concatenation or producing all pairs, is constant time.
The course’s list model is sequential: finding a member may require a scan. That is why an ID dictionary can be useful for repeated membership questions. A list remains useful when sequence and repeated occurrences matter.
Try it yourself
Can a True flag answer “which students”?
Show explained answer
No. It loses the IDs.
Try it yourself
Does a direct dictionary lookup require sorting its keys first?
Show explained answer
No.
Try it yourself
If all n students share one birthday and we print all pairs, can there be only n outputs?
Show explained answer
No. There are n(n−1)/2 unordered pairs; outputting them requires that many pair outputs.