About this video
This short video sets a challenge: build a machine that takes an integer X as input and outputs only true or false (a primality test). It introduces the two things we will measure about any such machine: how much time it takes, and how much space (rooms or memory) it needs.
You'll be able to
- describe the input and output of a primality testing machine.
- name the two resources we measure for a machine: time and space.
Key words
- input
- The information you give a machine to work on, here an integer X.
- output
- What the machine gives back, here just true or false.
- space
- How much room a machine needs: physical rooms for a mechanical calculator, or memory for a computer.
Transcript
Voiceover: We begin with a very simple question. Or not a question, a challenge. We need to build a machine which takes an input and that input is some integer X, and all that machine needs to do is output true or false. That is the first step. Now we will use the computer science tool to actually build this machine together.
One of the questions that we will be asking is two things, two aspects to this machine. How much time that a clock, how much time does it take to give the solution and how much space does it need? When I say space, I mean, for in the case of this mechanical calculator physical space, how many rooms do we need to hold our machine?
Or if we're using a computer, how much memory does it need? We will be returning to this two ideas as we go.
Video © Khan Academy, used under CC BY-NC-SA. Watch on Khan Academy. Puzzicle is not affiliated with Khan Academy.