Year 10 Digital Technologies · Creating Digital Solutions · 12m read

Algorithms — Efficiency, Searching and Sorting

Two programs can give the same answer but one takes a second while the other takes a day. Algorithm efficiency explains why.

Learning objective: Compare the efficiency of searching and sorting algorithms.

By the end of this lesson you can:

• I can trace linear and binary search.
• I can trace bubble, selection and insertion sort.
• I can compare efficiency informally (best/worst cases).

Binary search is finding a word in a dictionary. You don't start at page 1 — you open the middle, decide which half, and repeat. Each step halves the search, making it lightning fast on sorted data.

Algorithms — Efficiency, Searching and Sorting

SEARCHING:
• LINEAR — check each item; works on unsorted data; worst case n comparisons.
• BINARY — sorted data; halve each step; worst case about log₂ n comparisons.

SORTING:
• BUBBLE — swap adjacent items repeatedly.
• SELECTION — find the smallest, swap into place.
• INSERTION — insert each item into a sorted section.
• These simple sorts take roughly n² steps in the worst case; faster algorithms (merge sort, quick sort) are about n log n.

EFFICIENCY:
• Count comparisons/steps as data grows.
• Doubling the data doubles linear search time but adds only one step to binary search.

| Algorithm | Best for | Big-O (worst) |
|---|---|---|
| Linear search | Unsorted data | O(n) |
| Binary search | Sorted data | O(log n) |
| Bubble sort | Teaching, tiny lists | O(n²) |
| Insertion sort | Nearly sorted lists | O(n²) |
| Merge sort | Large lists | O(n log n) |

Key ideas at a glance

• Efficiency matters at scale: Big-O.
• Binary search needs sorted data: Precondition.
• Trace algorithms: Step tables.
• Divide and conquer: Merge sort.

Worked example (Medium)

Trace one pass of bubble sort on [5, 2, 4, 1].

1. Compare 5,2. Swap → [2,5,4,1]
2. Compare 5,4. Swap → [2,4,5,1]
3. Compare 5,1. Swap → [2,4,1,5]

Answer: After pass 1: [2, 4, 1, 5] — the largest value has "bubbled" to the end.

Worked example (Medium)

How many comparisons (max) for binary search on 1 024 items?

1. Halving. 1024 → 512 → … → 1.
2. Count. log₂ 1024 = 10.

Answer: About 10 comparisons.

Common mistakes

• Using binary search on unsorted lists It requires sorted data. Fix: Sort first.

Practice questions

1. Maximum comparisons for binary search on 1000 sorted items is about:

   1. 10
   2. 100
   3. 500
   4. 1000

   (1 marks)

2. Why is insertion sort good for nearly sorted data?

   (2 marks)

3. Binary search requires data to be:

   1. Random
   2. Sorted
   3. Text only
   4. Small

   (1 marks)

4. Explain why merge sort beats bubble sort on large lists.

   (2 marks)

Summary

• Linear vs binary search.
• Bubble, selection, insertion sorts.
• Efficiency grows differently with data size.
• Choose algorithms by efficiency.