Stretch tasks Efficiency and Searching Algorithms

Round 1: Quiz Blitz

1. Sorted It discards halves, which only works if the order shows which half to keep.
2. The target is last or missing Every item has to be checked.
3. 1000 In the worst case it compares every one of the n items.
4. 10 1,000 can be halved about 10 times before nothing is left.
5. True One more comparison halves the list one more time.
6. 15 23 is greater than 15, so the right half, 16, 23 and 42, is kept.
7. It does less work, not the same work faster Switching to binary search speeds up a program on exactly the same machine.
8. The data is unsorted; The list is short Sorted and large means binary. Unsorted, or small, means linear.
9. How many steps an algorithm needs Fewer steps means less time.
10. True Sorting costs far more than a single linear search saves.
11. Find the middle item → Compare it with the target → Discard the half that cannot contain it → Repeat until found or nothing is left Every comparison halves what is left to search.
12. The best case is luck and says little about the algorithm The worst case shows how the algorithm copes as data grows.

Round 2: Quick Fire

1. • Each comparison halves the remaining list
   • A million can only be halved about 20 times
   Model answer

   Each comparison halves the part of the list that is left, and a million can only be halved about 20 times before nothing is left.

2. • It works on unsorted data
   • So no time is spent sorting first, and it is simple
   Model answer

   Linear search works on unsorted data, so no time has to be spent sorting the list first.

3. • Best case: the target is the first item
   • Worst case: the target is last, or missing
   Model answer

   Best case: the target is the first item checked. Worst case: the target is the last item, or is not in the list at all.

4. • Find the middle item
   • If the target is smaller, keep only the left half
   • If it is larger, keep only the right half
   • Repeat until found, or until no items are left
   Model answer

   Find the middle item of the list. If it is the target, stop. If the target is smaller, keep only the left half; if it is larger, keep only the right half. Repeat until the target is found or there are no items left.

Round 3: Big Think

1. • Binary search should be used
   • Because the books are already in order
   • Each comparison halves the remaining list
   • So about 16 comparisons, instead of up to 50,000
   Model answer

   Binary search should be used, because the books are already sorted by ISBN. Each comparison halves the remaining list, so about 16 comparisons are enough to find any book, whereas a linear search could check every book, up to 50,000 comparisons.

2. • Efficiency is how many steps, or how much time, an algorithm uses
   • Compared by counting comparisons in the worst case
   • On large data the difference is huge
   • A better algorithm does less work, so it beats faster hardware
   Model answer

   Efficiency is how many steps, and so how much time, an algorithm uses to solve a problem. Algorithms are compared by counting their comparisons in the worst case. On ten items nothing matters, but on a million the difference is huge: a linear search might need a million comparisons where a binary search needs 20. A better algorithm does less work, so it speeds a program up on the same machine, without faster hardware.

This or That

1. Linear search Binary search needs a sorted list, and sorting it constantly would cost too much.
2. 7 comparisons 100 halves to 50, 25, 13, 7, 4, 2, 1: about 7 comparisons.
3. 6 It checks each item from the start, and 42 is sixth.
4. It doubles Linear search checks every item, so twice the items means twice the comparisons.
5. The target is first One comparison and it is found.
6. The target is not in the list Every half that could have held the target has been discarded.
7. One test of an item against the target Comparisons are the unit used to measure search efficiency.
8. No: efficiency shows as lists grow On tiny lists every algorithm is instant. Differences appear as the data grows.

Memory Match

• A 4 Linear search: Checks each item in turn
• B 5 Binary search: Halves a sorted list each time
• C 6 Worst case: The input needing the most steps
• D 3 Best case: The luckiest possible input
• E 2 Efficiency: How many steps an algorithm needs
• F 1 Middle item: What binary search compares first

Sort It

1. Linear search Simple to write and hard to get wrong Linear search is the simplest search.
2. Binary search One extra comparison each time the list doubles One more halving covers twice the items.
3. Linear search Works on unsorted data Linear search checks every item, so order does not matter.
4. Linear search Worst case of n comparisons for n items In the worst case every item is checked.
5. Linear search Checks each item in turn from the start That is how linear search works.
6. Binary search Needs a sorted list Binary search only works on sorted data.
7. Binary search Compares the target with the middle item Binary search always starts in the middle.
8. Linear search Best for a one-off search of unsorted data Sorting first would cost more than it saves.
9. Binary search Discards half of the remaining items each time That is what makes binary search fast.
10. Binary search About 20 comparisons for a million items Halving a million 20 times leaves nothing.