If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

Main content

# Algorithmic efficiency

## Video transcript

I have a report now that they are sending a new role a rover to Mars and we are responsible for doing one thing which is programming the algorithm inside the rover which checks if numbers are prime because let's say our Rover is communicating using RSA it needs an algorithm inside that can do a prime ality test now when you design a rover or anything to go into space you have to be very efficient in every way so the components used have to be very light the amount of power every subsystem uses has to be minimal you have to be saving energy and mass at every point in the design process so we have our work cut out for us because we have to be able to deal with numbers up to this size and it has to do it very fast so if we give it a very small input let's say just 90 it should be able to calculate that almost as fast as this entire number so as the input grows we don't want to see any of this noticeable slowdown now I want to analyze the user questions or the ideas users have had which were really good from mathematical standpoint we are checking if n is prime or composite so given some number n think of the space of all possible ends as say if n is 100 then this space is two to a hundred and what our algorithm is doing is its searching this space ok so you can think of algorithms as searching a space and at each point it's asking think of it as a step right a primitive step it's asking a question and it's actually a composite test the question so say this is a we're at number a we would say in the trial division method is n divided by a we just try this we drop a here and we try pen divides a and we see if the remainder is 0 which means a is a divisor of n then we can say ah we know 100% we raise the flag 100% sure its composite otherwise at each step we aren't quite sure it might be prime but we're not sure so we continue searching until we hit the end and remember our wall in this case was at the square root of n that's the worst case that unit situation occurs when we ends Prime we search all the way to the square root of N and then we can say ah it is prime and them are on 100% sure so in the case where n is even a multiple of two prime so 7 times 7 equals 49 if we throw 49 into our algorithm it is the worst case occurs we go all the way until the square root of n so the first set of questions from for example the 4th dimention asks once we rule out 2 as not divisible then all multiple 2 of 2 could be ruled out the same for 3 4 5 etc so that's a really great point our old algorithm was stepping along one at a time but we could be using patterns we know about composite numbers such as we know for sure that if a number is divisible by two then its composite if it's greater than 2 so 2 is prime but then we can say oh 4 is composite - oh I missed 5 here sorry about that 4 6 8 10 and instead we can take these step like this 3 5 7 9 so one category of questions they all try to reduce this space so if we eliminate all the even numbers now the check space instead of being up to the square root of n is the square root of n divided by 2 and we can find other patterns and composite numbers to try to make this even smaller the other type of question concerns the case where we find a composite witness that is we find an a that allows us to say oh we know n is composite Lola said wouldn't leaving the loop as as soon as we find prime check equals false cut down on some of the time and yes that's totally correct and it's something we want to do as soon as we are searching along using some step defined by whatever pattern we're using we find a composite witness that means it passes our test and we say 100% composite we should halt early we stop and say up we're done we won't continue searching and this halting early is great except it doesn't have to help us in the worst case which is if n is prime then the early halting won't help us and now we can visualize how these improvements allow us to reduce the space thus preventing as many checks happening inside the computer which depending on our computer will reduce the amount of time it takes so now I can show you the visualization I set up below which allows us to compare two algorithms based on how many steps occur during their execution on the left is algorithm a which is trial division which checks from two to the square root of N and on on the right is algorithm B which is let's just say our improved algorithm and in this case I've applied the check if it's divisible by two so we only do it half as many steps and I also terminate early in this algorithm B so it's not perfect I've just applied a few user modification so we can see what happens and now I'm going to just play with this to show you it here we can see as I scroll we see algorithm a we have the output whether it's composite or prime and at the bottom you'll see the number of steps so the first thing to notice is on the right-hand side every other number takes only one step and we know why that is because if it's an even number such as this it will quit so our old algorithm took 314 steps and our new algorithm only took one step because it checked if it was divisible by two so that seems like a really nice optimization however as we build our input you'll notice the steps increase and the bar grows and turns red once we hit the region when once we approach the region where we're going to crash so this red line up here is step limit if your bar hits there we fail which means our Rover would break and in this case the browser will actually crash so I'll try to get close to it so I'm close to it now and it's running very slow I can feel that my browser's just about to crash and give me the circle of death but notice that their improved algorithm took only two steps in that case but remember the worst case so I'm going to I have a few large prime numbers saved here for example we have to be able to handle any case we don't know what we're throwing at our algorithm so if I throw a large prime at it look what happens algorithm B as we know is taking half as many steps in the worst case but it's still taking many steps here because it's the worst case right so we're getting close to crashing here and this is not a very long prime we're still way under fifteen digits and when I put this twelve I think this is a 12 digit prime into our algorithm let's see what happens it's lagging it's late maybe it's going to crash look what happened both algorithms went way overboard so it didn't work our improved algorithm is not good enough yet but now we have an understanding of what we're trying to improve which is number of steps in the worst case and we also have this cool tool which allows us to visualize how fast it's growing how fast the number of steps grows as our input grows and below I'll explain how I set this up so you can set up your algorithm and compare it with the base case and see how much better you can do