CS10-08 Computer Science Watch
Which algorithm is more efficient?
In this lesson
Which algorithm is more efficient for GCSE Computer Science, with worked examples and the mistakes examiners report. AQA 8525 and Edexcel 1CP2 GCSE. Algorithms 8 of 9. More at https://scholafly.com
By the end: Explain that more than one algorithm can solve the same problem, compare two algorithms' time efficiency by counting their steps - comparisons and passes through a loop - for the same input, say which is more efficient and why in words that name what is reduced, and, for Edexcel, include memory use and test data in judging fitness for purpose.
What it covers
- 0:00 Intro: which algorithm is more efficient
- 0:35 Which algorithm is more efficient: time efficiency
- 2:31 The sentence that scores
- 4:39 Stop when it is found
- 6:12 Which algorithm is more efficient: memory use
Key words
About this video
Which algorithm is more efficient? | GCSE Computer Science | CS10-08
Which algorithm is more efficient for GCSE Computer Science, with worked examples and the mistakes examiners report.
AQA 8525 and Edexcel 1CP2 GCSE. Algorithms 8 of 9.
More at https://scholafly.com
Watch first: CS10-06 - https://youtu.be/u0VAKp0NrxI
Video code: CS10-08 (search "ScholaFly CS10-08")
#GCSEComputerScience #Algorithms
For teachers
This GCSE Computer Science lesson teaches which algorithm is more efficient?. By the end, students should be able to explain that more than one algorithm can solve the same problem, compare two algorithms' time efficiency by counting their steps - comparisons and passes through a loop - for the same input, say which is more efficient and why in words that name what is reduced, and, for Edexcel, include memory use and test data in judging fitness for purpose. It works through four worked examples and the mistakes examiners report.
Exam board specification references:
AQA 8525
- 3.1.2
Edexcel 1CP2
- 1.2.7
- 6.1.6
Read the transcript
Two friends hunt for one name in five hundred phone contacts. One scrolls from the top; the other types the first letter and jumps there. Who did better? Both found the right name, so it is tempting to call it a draw. It is not, because one method took far fewer moves. When a question asks which algorithm is more efficient, the answer is not a feeling. It is a count.
More than one algorithm can solve the same problem, and all of them can be correct. Efficiency is how they differ. Time efficiency means taking fewer steps for the same input, so the algorithm finishes in less time. The steps are counted, never guessed. Two counts are used: the number of comparisons, where two values are checked against each other, and the number of passes through a loop. Algorithm A uses a loop to total the numbers from one to a hundred, one number per pass. Algorithm B uses one formula: n, times the bracket n plus one, all divided by two. Both give five thousand and fifty. Which is more time efficient, A with its loop or B with its formula, and why? B. A makes a hundred additions, one each time round. B does one calculation, whatever n is. A loop can look like more programming, but here it means more work, not less. One examiner's report records the opposite belief: "One common misunderstanding was that since Program A used an iteration structure it must be more efficient, when in fact the opposite was true in this case." The fix is to count, every time, and never judge an algorithm by how its code looks.
Saying which algorithm is more efficient is half an answer. The other half says what is reduced, and what that saves. Three answers to the formula question. One: B is more efficient. Two: B has fewer steps. Three: B makes fewer calculations, so it takes less time. Which of the three answers is complete, and what do the other two leave out? The third. The first never names what is reduced, and the second never says what that saves. The sentence has a shape: B is more efficient because it does fewer calculations, so it takes less time. The measure goes after because, and the saving goes after so. One examiner's report puts the slip in two sentences: "As with the previous specification, students are still using efficiency as an answer without qualifying what they mean. Students often said that 'B has fewer steps' without adding that this would therefore make it more 'time efficient' or 'reduce the number of calculations required'." The fix is the shape: name the measure and the gain, such as fewer comparisons, so it takes less time. A report on another paper notes: "Most candidates scored full marks for this question for correctly identifying the relationship between the number of comparisons and execution time." So the habit is to write that link down every time, rather than leave it in your head.
Passes through a loop are a cost too, and stopping once the answer is found in the data cuts them. Two algorithms check whether a number is in a list. Algorithm E always checks every item. Algorithm F stops the moment it finds the number. Seven is third in a list of ten: how many comparisons does each algorithm make? E makes ten, because it never cuts short. F makes three, halting at seven. Now, does that gap depend on where seven sits in the list? Yes. If seven were last, both would make ten comparisons. The early exit saves time only when the item turns up early. Another report records the same waste: "Other responses used an iterative loop and processed every item in the data, ignoring the requirements for an early exit." The fix: once the answer is found, stop. Every pass after that is time spent for nothing.
Time is the only measure some courses ask about. Another course also asks about memory, and about whether the algorithm works at all. Memory use is how much storage an algorithm needs while it runs, such as how many variables or copies of data it keeps. Algorithm C swaps the values held in two variables, using one extra temporary variable. Algorithm D makes a full copy of a list in a second list, then works on the copy. Which of C or D needs more memory, and when would the difference matter? D, by far, because it holds everything twice. C adds one small slot. The gap matters with very large data, or on a device short of memory. Fitness for purpose comes before any count. An algorithm meant to pick out the biggest number in a list runs very fast. It is very fast, and given three, eight and two it outputs three. Is it fit for purpose? No. The answer should be eight, so it is wrong, and a fast wrong answer is no use. Test it with data first, then compare counts. You may meet formal notation for efficiency online. It is not needed here, and one course's specification says so: "Formal comparisons of algorithmic efficiency are not required." Counts for a given input, and a plain sentence, are the whole answer.
Count first, then say what the count saves: the questions follow that order. P makes twenty comparisons and Q makes eight on the same input. Write the sentence. Q is more efficient because it makes fewer comparisons, so it takes less time. Try this: does a loop always make an algorithm more efficient? No. A loop can mean more passes and more work, and only the count can tell. Another: Sam is second in a list of twenty names. What does an early exit save? Eighteen comparisons. It stops after two instead of checking all twenty, so no passes are wasted. One more, the two friends and the contacts list: which was more efficient, and why? The one who jumped, because they made far fewer moves for the same name, so it took less time.
This video joins the chapter list. A thumbs up logs it as learned once you have fully understood it, and you can pass over it later; whatever has no thumbs up is still yours to come back to. If it is still fuzzy, keep it saved and return to it later in the week, once the counting has had time to settle.
Next in the chapter: Which notation do you answer in, for each course's exam papers. Hopefully that's next in your feed, but if not, search for ScholaFly C S ten, oh nine.
Every other video is on scholafly.com too, easy to search by video code or by keyword. Whatever you're revising, go there and have a look, or, watch the next video.
Related terms
For: AQA GCSE 8525, Edexcel GCSE 1CP2
On the specification
| Board | Spec | Statement |
|---|---|---|
| AQA GCSE 8525 | 3.1.2 | Explain that more than one algorithm can solve the same problem and compare the time efficiency of two algorithms. |
| Edexcel GCSE 1CP2 | 1.2.7 | Use logical reasoning and test data to evaluate an algorithm's fitness for purpose and efficiency, counting compares, counting passes through a loop, and considering memory use. |
| Edexcel GCSE 1CP2 | 6.1.6 | Use logical reasoning and test data to evaluate a program's fitness for purpose and efficiency, counting compares, counting passes through a loop, and considering memory use. |
For teachers
This GCSE Computer Science lesson teaches which algorithm is more efficient?. By the end, students should be able to explain that more than one algorithm can solve the same problem, compare two algorithms' time efficiency by counting their steps - comparisons and passes through a loop - for the same input, say which is more efficient and why in words that name what is reduced, and, for Edexcel, include memory use and test data in judging fitness for purpose. It works through four worked examples and the mistakes examiners report.