MskProdComputing
Back to the topic

The mark scheme starts on a new page, so you can print pages one and two for a student and keep the last page yourself. Everything prints in black on white whichever theme you are using.

AQA GCSE CS · 3.1.2, 3.1.3

Efficiency and Searching Algorithms

Section A: 10 multiple choice questions, 10 marks. Section B: 5 written questions, 16 marks. Total 26 marks.

Name

Class

Date

Mark  / 26

Section A

Circle the letter of the correct answer. One mark each.

  1. 1What condition must be met before a binary search can be used?1
    1. AThe list must have an even number of items
    2. BThe list must be sorted
    3. CThe list must contain only numbers
    4. DThe list must be stored in RAM
  2. 2A linear search is performed on a list of 500 unsorted names. What is the maximum number of comparisons needed?1
    1. A1
    2. B9
    3. C250
    4. D500
  3. 3Roughly how many comparisons does a binary search need in the worst case on a sorted list of 1000 items?1
    1. A10
    2. B100
    3. C500
    4. D1000
  4. 4Which is the single advantage of linear search over binary search?1
    1. AIt uses less memory per comparison
    2. BIt needs fewer comparisons
    3. CIt can search two lists at once
    4. DIt works on data that is not sorted
  5. 5A binary search is looking for 30 in [10, 20, 30, 40, 50, 60, 70]. Which item is compared first?1
    1. A10
    2. B30
    3. C40
    4. D70
  6. 6If a sorted list doubles in size, how does the worst case for a binary search change?1
    1. AIt increases by one comparison
    2. BIt increases by half the list length
    3. CIt stays exactly the same
    4. DIt doubles
  7. 7Which statement about the efficiency of an algorithm is correct?1
    1. AA more efficient algorithm completes the same task in fewer steps on the same hardware
    2. BEfficiency is measured in bytes of source code
    3. CEfficiency only matters for programs that use the internet
    4. DA more efficient algorithm requires a faster processor
  8. 8Data arrives in a random order and each item is searched for only once before the data is replaced. Which approach is best?1
    1. ANeither search can be used on random data
    2. BLinear search, because sorting first would cost more than the search saves
    3. CSort the data then use binary search, because binary search is always faster
    4. DSort the data twice then use linear search
  9. 9How many comparisons does a linear search need to find 4 at the start of [4, 8, 15, 16, 23, 42]?1
    1. A0
    2. B1
    3. C3
    4. D6
  10. 10Why is the worst case, rather than the best case, normally used to compare algorithms?1
    1. AThe worst case is always the same for every algorithm
    2. BThe best case only applies to sorted data
    3. CThe best case depends on luck and says nothing about how the algorithm behaves in general
    4. DThe best case is impossible to calculate

Section B

Answer in the space provided. The number of marks tells you how many separate points to make.

  1. 1DescribeDescribe how a binary search finds a value in a sorted list.4
  2. 2StateA list of 1024 sorted values is searched. State the maximum number of comparisons required by a linear search and by a binary search.2
  3. 3ExplainExplain one advantage of a linear search over a binary search.2
  4. 4JustifyA company stores 5 million customer records, sorted by customer number, and looks up records thousands of times each hour. Justify which search algorithm they should use.5
  5. 5ExplainExplain why comparing the efficiency of two algorithms is more useful than comparing how long each takes to run on a particular computer.3

Mark scheme

Section A

1B2D3A4D5C6A7A8B9B10C

Section B

1 Describe how a binary search finds a value in a sorted list. 4

One mark for each of the following, to a maximum of 4.

  • The middle item of the list is examined
  • If it matches the target the search stops
  • If the target is smaller the upper half is discarded, and if larger the lower half is discarded
  • The process repeats on the remaining half until the item is found or no items remain

Model answer. A binary search first examines the item in the middle of the sorted list. If that item is the one being searched for, the search stops and reports success. If the target is smaller than the middle item then every item to the right of the middle can be discarded, and if it is larger then every item to the left can be discarded, because the list is in order. The search then repeats on whichever half remains, examining its middle item, and continues halving until the target is found or until no items are left, at which point the value is known not to be in the list.

2 A list of 1024 sorted values is searched. State the maximum number of comparisons required by a linear search and by a binary search. 2

One mark for each of the following, to a maximum of 2.

  • Linear search requires up to 1024 comparisons
  • Binary search requires up to 10 or 11 comparisons

Model answer. A linear search must compare every item in the worst case, so it requires up to 1024 comparisons. A binary search halves the remaining list at each step, and 1024 can be halved ten times to reach a single item, so it requires at most about ten or eleven comparisons.

3 Explain one advantage of a linear search over a binary search. 2

One mark for each of the following, to a maximum of 2.

  • A linear search does not require the data to be sorted
  • So it can be used on data that arrives in a random order, or where sorting would cost more time than it saves

Model answer. The advantage of a linear search is that it does not require the list to be in any particular order, whereas a binary search only works on sorted data. This means a linear search can be used immediately on data that arrives in a random order, and for a list that is searched only once it is often faster overall, because sorting the list first would take considerably more time than the linear search itself.

4 A company stores 5 million customer records, sorted by customer number, and looks up records thousands of times each hour. Justify which search algorithm they should use. 5

One mark for each of the following, to a maximum of 5.

  • Binary search should be used
  • The data is already sorted, which is the condition binary search requires
  • Binary search halves the number of remaining records with each comparison
  • So it needs about 23 comparisons rather than up to 5 million
  • The saving is repeated on every one of thousands of lookups per hour

Model answer. The company should use a binary search. The records are already sorted by customer number, so the one condition that binary search requires is satisfied and no sorting cost has to be paid. Binary search compares the target with the middle record and then discards half of the remaining records, repeating until the record is found, so the number of comparisons grows extremely slowly as the data grows. On five million records it needs roughly twenty three comparisons in the worst case, whereas a linear search would need up to five million. Because the system performs thousands of lookups every hour, that saving is multiplied thousands of times over, so the difference between the two algorithms is the difference between an instant response and a system that cannot keep up.

5 Explain why comparing the efficiency of two algorithms is more useful than comparing how long each takes to run on a particular computer. 3

One mark for each of the following, to a maximum of 3.

  • Run time depends on the hardware the program is tested on
  • Efficiency counts the number of steps or comparisons, which is independent of the machine
  • So efficiency predicts how the algorithm will behave as the amount of data grows

Model answer. The time a program takes to run depends on the computer it is tested on, so a poor algorithm on a fast processor can appear quicker than a good algorithm on a slow one, which tells you nothing about the algorithms themselves. Measuring efficiency instead counts the number of steps or comparisons the algorithm performs, and that count is a property of the algorithm rather than of the hardware. It also shows how the work grows as the data set grows, which is what actually matters, because two algorithms that look identical on a hundred items can differ by a factor of thousands on a million.