Trace Search and Data Tradeoffs

Retrieval Prompts

1. What condition must be true before binary search is valid?
2. In plain language, what does Big O describe?
3. Why can arrays feel fast for reads but awkward for middle inserts?
4. What makes a hash table fast on average?
5. Why is O(log n) not just "a little better" than O(n) on very large inputs?

Compare and Distinguish

Compare these pairs in one or two sentences each:

• simple search vs binary search
• array vs linked list
• array vs hash table

Do not answer with slogans like "one is faster." Name the operation and the reason.

Common Mistake Check

If you wrote "hash tables are always O(1)" without saying "average case" or without mentioning collisions, your explanation is too loose.

If you wrote "binary search is faster" without naming sorted order, your explanation is incomplete.

Mini Application

Create a table with these columns:

Scenario	Best first-fit choice	Why

Fill it for at least four scenarios, such as:

• phone-book style lookup in sorted data
• username lookup
• reading the tenth element often
• frequent insertions in the middle
• storing key-value prices for many products

Then add one extra row from your own life or work.

Evidence Check

You are done only when:

• you traced at least one successful and one failed binary search
• you wrote at least one Big O explanation without using stopwatch language
• you chose structures by operation, not by buzzword
• at least one of your scenario justifications names a tradeoff, not just a winner