So, let's begin with the basic challenge.

In this challenge, it's been with us since the very early days of computing.

In fact, it goes back to Babbage who built this machine called the Difference Engine.

That's a mechanical machine that was

going to perform arithmetic operations like multiplications.

This is actually a copy that was built in the '90s

at the British Science Museum, London Science Museum.

Here's what Babbage said,

"As soon as an Analytical Engine exists,

it will necessarily guide the future course of the science.

Whenever any result is sought by its aid,

the question will arrive by what course of calculation

can these results be arrived at by the machine in the shortest time?"

In this machine, if you look at it,

it actually has a crank.

So really Babbage's question was how many

times do you have to turn the crank to get your answer?

Really, that's what we're talking about today is how can we be

sure that we're getting the results in not maybe not the shortest time,

but at least a reasonable amount of time.

It's a very important thing to have in mind when we're crafting

programs to solve scientific and commercial problems.

So, the more modern version of this,

this is our review where we were in program development,

where we test our program,

we get it compile, run,

and test, and then after a while,

we start using it to solve a practical problem.

But really if it won't solve the practical problem,

it might be just because it's too slow, it's too inefficient.

So we want to talk today about how might you understand its performance characteristics,

so that you can approve it,

and actually address the practical problem.

The key insight behind this was developed by Knuth and the 1970s,

who pointed out that it really is feasible and

actually productive to use the scientific method to understand performance.

That's what we're going to talk about today.

So there's a lot of reasons to study program performance.

Here's three in particular.

So one is we want to just predict the behavior of our program.

We want to know if it will finish at all.

Is it in a loop, or is it just taking a long time?

Actually, usually, we want to know when will my program finish.

But we also might want to compare algorithms and implementations.

We want to know, "Well,

I've got a program that works,

but if I change it in this way,

will it make my program faster?"

or "How can I make my program faster?"

That's another reason that we might want to study performance.

So making a distinction between the word algorithm and the word program,

an algorithm is the general method for solving

a problem that's suitable for implementation as a program.

We're going to study a lot of algorithms in this course,

and if you take more CS courses,

you'll see plenty of them.

This is our book on algorithms,

and we have two courses on algorithms later on online.

So, really, what we want to do is with studying

performance of algorithms and programs is to develop

a basis for understanding the problem and for designing

new algorithms or maybe setting parameters that make the algorithms work best.

This is really where we get at

new technology problems that we

could solve with a clever algorithm that couldn't otherwise be

solved or addressed at all or research problems that we can

feasibly address with a good algorithm that we cannot feasibly address without it,

and I'll give some examples of this later on.

So we had some fairly complicated programs.

This is our gambler simulation that we did early on is a example of nested loops.

If you run this for large values of the parameters,

it might take quite a while to run,

and the question is when is it going to finish?

How long is it going to take to finish?

That's just one example.

For many, many of the programs and algorithms we consider,

we want to have some idea of when they're going to finish.

So just to motivate this further,

I'll give some specific examples.

So first one is N body simulation problem.

We looked at a program for doing that on a display, but, more generally,

the value of N could be really large,

like astrophysicists are interested in studying these interactions for huge,

huge values of N. The algorithm that

we looked at to solve this problem took time proportional to N squared.

So that we call that quadratic time, and we'll talk about that.

As the problem size increases,

the time increases as a function of N squared.

Well, in the '70's,

this became a problem because that value way,

way exceeded the limit on the available amount of time that was available in a computer.

You can run your fastest computer for a year,

and you still can't solve the problem for values of N that you'd like to solve it.

But the success story is an algorithm known as

the Barnes-Hut algorithm that solves the problem in NlogN steps,

and therefore enabled scientists ever since then,

and they still use this algorithm,

to push their understanding of this problem to huge,

huge values of N, really enabling

new research on understanding properties of the universe.

This algorithm was actually invented in research started by

Andrew Appel who's a professor at Princeton but

did this for his senior thesis as an undergraduate.

So that's a perfect example of

the importance of finding an efficient algorithm to solve a problem.

Here's another one, the discrete Fourier transform.

This is a very fundamental calculation.

In signal processing, I'm going to break down a waveform into its periodic components.

Again, the straightforward algorithm

for solving this problem is quadratic in the problem size.

Again, that algorithm quickly hit the limit of

available time on computers even as early as the '50s and '60s.

So you couldn't really do this

to address the commercial problems that people cared about.

But turns out there's an algorithm known as the FFT,

the fast Fourier transform.

It actually has origins in classical mathematics dating back to Gauss

but was popularized by John Tukey,

Cooley and Tukey in the 1950s.

That algorithm uses NlogN steps,

and so therefore ever since that time,

people have been able to push the size of problems they can

solve FFTs on to a very huge limit way below the limit on available time.

That's the basis for a lot of the technology that we have surrounding us

from MRI machines to music players,

and game players in cell phones is based on our ability to solve this problem quickly,

another example of the importance of having a fast algorithm.

So, really, the design of fast algorithms is a subject of a later course, but for now,

what we want to do is at least provide a basis for how

you can understand the performance characteristics of your programs.

Now I need one technical thing,

we use binary logarithms in a lot of our analysis,

and I just want to get this notation out of the way.

So, the binary logarithm of a number is the number x such that two to the x equals N,

and it grows very slowly.

Any computer scientist knows this.

This is the number of bits that is needed to express N in binary.

So, any computer scientist knows that two to the 10th is about 1,000 of

the binary logarithm of two to the 10th is about 10 is exactly 10.

Two to the 20th is about a million and a binary log is 20 and a billion is 30.

So that's just a really quick computer science calculation,

when we say log,

think a billion, think 30.

This is a much smaller number than a billion is the main point.

So, like when we had this recursive convert program

that converts a number from a decimal to binary or prints out the binary representation,

that's actually the largest integer equal to log N,

some number of bits there,

and we write that as a floor of log N as largest integer less than or equal

to log N. We can prove that by induction.

We do actually talk about that later on.

So, the number of bits in the binary representation of N is about binary log of N,

and it rises often in the study of recursive problems,

and including like the FFT and the Barnes Hut.

So, this divided half idea is what brings out

a logarithm and we'll see examples of that later on in the course.

So, what we're going to use as an example to

study performance is called the three-sum problem.

It's a very simple problem.

Given N integers we want to know how many of the triples those integers sum to zero,

they could be positive or negative.

Now, these other processes that we might want to perform on those triples,

but for now, for simplicity, we're just going to count them.

Let's say our problem is to find out how many there are.

So, this problem actually turns out to be

a very fundamental problem in computational geometry.

That's a computer algorithms to process a geometric algorithms.