- [Craig] In this video, we'll be taking a look at algorithm efficiency.
(uplifting piano jingle)
There are four algorithms you need to know about for the GCSE.
There's two searching algorithms, the binary and linear search,
and two sorting algorithms, the merge and bubble sort.
We have separate videos in this section that look at each of these in depth.
In this video though,
we're focusing on algorithm efficiency.
So which version of each of these is more efficient?
And what do we even mean by the efficiency of an algorithm?
Well, talking about the efficiency of an algorithm is actually quite a complex process,
and we look at this in depth in the later half of the video when we go beyond the GCSE specification.
But the point of view of your exam,
we're simply meaning here which algorithm is typically quicker at performing a task on a data set.
So let's have a look at the two algorithms presented here.
You can see we have two procedures called sum integers
and they both take in one parameter, n, and that's a number.
If n is supplied with 10, then both algorithms perform the calculation
1 plus 2 plus 3 plus 4, all the way up to 10.
Again, if n was 100,
it would perform 1 plus 2 plus 3 plus 4, all the way up to 100.
So both algorithms here do exactly the same thing,
but you can see they've been implemented or coded in different ways.
So which one would execute quicker?
In simple GCSE terms, which one is more efficient?
If we take the algorithm on the left,
we can see there's a line of code here which has to be executed,
and that is assigning the value zero to sum.
So I've written that out there below.
And then you can see we have this line of code to execute.
And it says sum becomes equal to the current value of sum plus n.
So if we assume n is 10, for example,
so that's the value of the parameter that you've passed in,
then this line of code would execute 10 times.
The first time around the loop, it would perform the calculation nought plus one.
The second time, one plus two, and then three plus three.
So there's 10 additional lines of code that need to be executed
and I've written those out below as well.
On the right here, we can see that we have again a single line of code.
Sum becomes equal to n times n plus one divided by two.
That's not inside an iterative statement like a for loop.
That line of code simply runs once and that is it.
So even though both algorithms do exactly the same thing,
the left-hand version takes far longer to execute.
Indeed, if we take this to the extreme and imagine increasing the value of n to a million,
then the left-hand version would take significantly longer,
whereas the right-hand version would be just as quick
no matter what the value of n was entered.
So now we've covered the basics,
let's look at a couple of scenarios regarding algorithm efficiency
that you are specifically required to know about for the exam.
The first is best- and worst-case scenarios for linear search versus a binary search.
So here we have a sorted list.
It has 100 data items in it and we can see their index from 0 to 99.
And then they contain a set of integers.
So in index position 0 is the integer 3, all the way up to index position 99
that contains the value 989.
Now in a best-case scenario, a linear search will find an item in an ordered list after just one comparison.
And of course, this would happen if the item we were trying to find was located in the first element of the data set.
Of course in a worst-case scenario, a linear search will find an item in an ordered list after n comparisons,
where n is the actual size or number of elements in the list.
And of course, this would happen if the item we were trying to find was located in the last element of the data set.
So in our example data set, in a linear search, the best case would be one comparison
whereas the worst case would be 100 comparisons.
Okay, so now let's think about a binary search, and we'll start again with best case.
And in a binary search, in a best-case scenario,
we'll find an item in an ordered list after just one comparison.
This happens if the item we're trying to find was located at the midpoint of the data set.
And this is because the fundamental concept of a binary search is we start by looking at the mid value,
which is done by taking the left pointer and the right pointer and doing an integer division by two.
So that's 0 plus 99 equals 99.
Integer division by 2 is 49.
And that gives us the place where we look.
If the value is found then we stop the search and if not, we discard half the list and we carry on.
So given our example data set shown here, what would be the worst case?
How many possible comparisons might a binary search have to make?
Well, we'll assume the item is not in the midpoint.
So we discard half the list and of course,
the half the list we discard depends if the number we're looking for is less than or greater than the midpoint.
We check the new midpoint and discover this still isn't the item we're looking for because we're going for a worst case.
So again, we discard half the list.
Now as you can see, in each situation, we're assuming the item we actually want is in the lower half.
So we keep discarding the greater half of the list.
We're now down to 24 data items in elements 0 to 23.
We check the midpoint, 11.
The item still isn't there, so we discard the right-hand half of the list.
Again, we calculate and check the midpoint, it's still not there.
So we discard the right-hand half of the list,
we calculate the midpoint, it's not what we're after.
So we discard the right-hand part of the list,
we check the midpoint, it's not the item we want.
So we discard half the list
And now we're down to a single item.
So the midpoint is the same as the only element left and now,
we obviously have found it but it's the worst-case scenario,
it was the last possible item left.
So in our example data set,
a binary search best case took one comparison,
whereas a binary search worst case took seven comparisons.
And if you remember back to our previous example with the same data set,
although the best case is the same, just one comparison,
the worst case for linear search was 100.
So we can see here that a binary search is much more efficient, especially in worst case.
And this gets better and better as the size of the data set increases.
You also need to consider in place versus out of place algorithms.
So this refers to the bubble sort and the merge sort algorithms.
Bubble sort is an example of an in place algorithm.
That's an algorithm that transforms the input without using any extra memory.
As the algorithm executes,
the input is usually overwritten by the output and no additional space is needed.
Now that's not to say an in place algorithm won't require a small amount of extra memory for its operation,
but the amount of memory required must not be dependent on the size and should be constant.
So we can kind of ignore it and call this an in place algorithm.
A merge sort, however, is an out of place algorithm
and this requires extra memory depending on the input size.
The standard merge sort algorithm is an example,
as it requires extra memory for the splitting and merging process.
Well that is certainly enough for the GCSE specification
to get you to appreciate that although many algorithms can be written to perform the same purpose,
it doesn't necessarily mean they are all as efficient as each other.
However, if you're finding the topic of algorithms quite interesting,
you can put your pen down now and we're going to go over some of the content which will be covered in the A Level,
and it will make a great introduction to that part of the course.
So when we talk about algorithm efficiency,
especially beyond GCSE, we can measure efficiency in two ways.
We have the time complexity, so that's how much time an algorithm needs to solve the problem,
and we have space complexity, so that's the amount of resources,
e.g., memory, the algorithm requires to complete.
Some algorithms are more efficient time-wise than others,
whereas others are more efficient space-wise than others.
If you just go back to the example we looked at in the previous part of the video,
we can go a step further now that we're going beyond the GCSE spec.
Let's ignore that first line of code that's executed because it's only executed once,
whereas the blue line is executed 10 times.
It's the significant part of this algorithm.
Indeed, as the value of n grows,
if n was 100 or 1000,
the fact that that first red line is executing once really becomes very insignificant.
So if we just focus on the blue line,
we can see here that this algorithm has what we call a linear time complexity.
The algorithm's performance declines in a constant and direct relation as the size of the data set grows.
The version of the algorithm on the right has a constant time complexity.
The algorithm is always going to execute in the same time regardless of how big the value of n is.
Now, these words constant and linear are actually something you'll learn about at A Level.
You're starting to notice we can now compare algorithms by expressing how complex they are as a function
relative to the size of the problem they're trying to solve.
And Big O notation is a special way for classifying algorithms
based on how their computational times grow as their input size grows.
On the screen here are a range of Big O notations and some descriptions.
Again, if we just look back at the example we covered at the start of the video,
you can see here the left-hand version of our original algorithm has a linear complexity,
whereas the right-hand version has a constant complexity.
It's a much more efficient version of the algorithm.
We know that algorithms are some of the hardest parts of any computer science specification,
so we've written a book called Essential Algorithms for A Level Computer Science,
which is available on Amazon.
While the title of the book suggests this is only for A Level, you can see here from the examination board mapping page
that we have chapters which cover every algorithm you're required to know for the GCSE.
This book then would be perfectly appropriate for you to use
and also to take on to A Level should you choose to carry on studying the subject.
Every chapter is presented in the same way.
We introduce the algorithm from a high-level perspective and provide a link to our videos.
We then lay out the algorithm in simple, structured English so you can get your head around it.
We illustrate the algorithm in the form of a diagram and then provide an example of stepping through it.
All of these steps are designed to really get you to understand the algorithm before we present you with pseudocode.
After the pseudocode, we present you with actual code written in both Python and Visual Basic,
which you could type in and try for yourself.
(uplifting piano jingle)