[Unit 5 - How Programs Run, Making Things Fast]
Welcome to Unit 5. The main topic for this unit is trying to understand the cost of running program.
So far we haven't really worried about this. We've been very happy to write code.
If we get the correct result, that's a great thing.
But once we start making programs bigger, worrying about programs that do more things,
running on larger inputs, we have to start thinking about the cost of running our programs.
This question of what it costs to evaluate an execution
is a very important problem in computer science.
Sometimes it's one of the most fundamental problems.
Many people spend their whole careers working on this.
It's a problem called algorithm analysis.
I haven't yet explained what an algorithm is, but you've actually written many of them already.
An algorithm is the procedure that always finishes.
A procedure is just a well-defined sequence of steps.
It has to be defined precisely enough that it could be executed mechanically.
To be a procedure, it has to be something that can be executed without any thought.
We're mostly interested in procedures that can be executed by computers,
but the important part of what makes it a procedure is that the steps are very precisely defined
and don't require any thought to execute.
To be an algorithm, it has to always finish.
We've pointed out already that this is a very tough problem--
to figure out whether a program will finish.
In general, it's not possible to answer that question,
but for many specific programs it is.
In order for a program to be an algorithm, we have to know that it always finishes,
and it always produces the correct result.
Once we have an algorithm, we know we have a well-defined sequence of steps,
so we can reason about what will happen on any input.
And we know that it will always finish and always produce the correct result.
Then we can think about what the cost is of executing that algorithm on some input.
How should we think about cost?
The way computer scientists think about cost is quite different
from how most people think about cost.
If you're normally thinking about cost, you've got a specific object.
Let's say you've got a cool car. This is supposed to be a cool car.
It doesn't quite look like a cool car. It's got a cost associated with it.
Let's say that's a $25,000 car, and you have some other car.
You have one car that's got a particular cost. That's what it costs you to get that car.
You could have another car that would be smaller and green.
Let's say that car costs $10,000.
When we think about the cost of things normally, we have very specific things.
They have specific costs, and we know that the red car costs $25,000,
the green car costs $10,000. The red car costs more than the green car.
We just need to compare those costs.
When we think about the cost of algorithms,
we don't have a specific execution in mind usually.
What we want to understand is how the cost depends on the input.
We might have two different algorithms, let's say this is algorithm 1,
and we have a second algorithm that solves the same problem.
Both of these are algorithms that take inputs and produce output.
If we wanted to decide which algorithm is better,
we don't have a specific cost for the algorithm the way we do for the cars.
We can say the red car costs more than the green car.
The cost depends on the actual input that we run the algorithm on.
It might be the case for some inputs algorithm 1 is faster,
and for other inputs, algorithm 2 is faster. I should label this algorithm 2.
What we need to understand is how the cost of executing the algorithm depends on the input.
We don't want to do that for every specific input.
If we had to do that for every input, we might as well just run it on the input and see what it costs.
What we want to do is be able to predict this without actually having to run it on every input.
Normally, there isn't that much that matters about the specific input.
The main thing that's going to matter about the input is the size of the input.
That's not always going to be the case, and we'll see examples where other properties of the input matter.
The primary way we talk about cost in computer science is based on the size of the input.
As the size of input increases, how does the cost to evaluate the procedure increase?
Cost ultimately always comes down to money.
When it comes down to money what are the things that cost money when we execute algorithms?
The main things that cost money are the time it takes to finish.
If we get an answer more quickly, we've spent less time on it.
We can also rent computers by the time to execute.
There are lots of cloud computing services now that will give you a processor of a certain power
for a certain amount of time for a certain number of cents per hours.
Time really is money, and so we don't need to turn our cost estimates into money,
because we don't necessarily know how much our computing cost will be.
But if we can understand the time it takes to execute,
that'll give us a good sense of the cost.
The other main cost is often memory.
If we know that we need a certain amount of memory to be able to execute our algorithm,
that tells us something about the size of computer we need
and how expensive that's going to be.
We don't usually talk about cost in terms of dollars when we analyze algorithms.
We're talking about cost in terms of time and memory,
but those things in real implementations end up being cost in terms of dollars.
We're mostly going to focus on measuring time,
and time is usually the most important cost of running an algorithm.
Memory is often another consideration.