Our last topic for Chapter 1 is complexity.
And that's a- it's gon- it's a very rough measure
of how- how long does it take on a computer,
uh, to carry out, uh, a certain operation.
It's something we'll be talking about,
uh, throughout the course.
Okay. So the way this works is computers store,
uh, a real number in floating point format.
Now, in this course, you don't have to know what that is.
Uh, but what it is, is it- it allows you it
doesn't- it doesn't represent the number exactly,
but it's very, very close.
So for example, it wouldn't- it wouldn't store the number one-third exactly as one-third,
but it would store it as like 0.33333 with about 15 threes in there, right?
Which is for all practical purposes, close enough.
Okay. Now, when you take a- a basic,
when you ask a computer to carry out a basic operation on two floating point numbers,
like you ask it to add or multiply them or divide them or subtract.
Now that's called a floating point operation or,
and the slang for that is flops.
That's a flop. A single flop is adding two numbers on a computer.
Okay. Now when you have an algorithm or an operation and you wanna, uh,
what you do is the- the complexity of it, uh,
is judged by simply counting up the total number of flops,
uh, that it's- that you're going to need to do.
Uh, so for example, you might count the number, uh,
both times you have to multiply two numbers, add two numbers,
subtract or divide them,
and you add up all those numbers together.
And that- that's called the flop count for your, uh, operation.
Okay. Now, it turns out this can be very grossly approximated because implicit in
this is the idea that adding two numbers comes at
the same cost is dividing two numbers, which is false.
It actually takes longer to divide two numbers.
However, still, this is just meant to give you a rough idea
of whether [NOISE] carrying out an operation is going to cost you.
Is it going to be done in way under a second- a second,
a minute, an hour, a day.
That's- that's really what we're aiming for with this very crude estimate.
Okay. Now a crude approximation
of how long at times it takes for a computer to actually carry out,
uh, that, uh, that set of operations,
or that operation is this.
It's the number of flops you need,
uh, to carry out, uh,
divided by the computer speed and then it computer speed is given in,
uh, flops per second.
Okay? So you can see that flops into divided by flops per second gives you seconds.
So it tells you - it tells you how long it's gonna take in seconds.
Now, this is very crude approximation.
We would not- we certainly don't expect this to be even like,
you know, accurate within plus minus twenty percent.
And in fact, it could even be - be off by big factor,
like a factor of ten or more.
But it - it doesn't distinguish between seconds and hours that it can actually do.
Okay, now a current computer is around
a- can carry out or run a billion flops per second.
Uh, actually, my phone can carry out a billion flops per second.
So, uh, and a- my laptop can do maybe 10.
Uh, but fancier computers,
GPUs, for example, gra- you know, graphical processing units.
They can actually carry out even much more than that.
Uh, they can, some of them can even,
actually, many of them now can actually carry out,
not just, uh, they can actually carry out ten to the twelve flops per second.
That's- that's a thousand billion to trillion flops per second.
That's called a teraflop,
uh, per second computer.
Okay. Ah, so let's just do a quick example.
Um, and let's say that you have an operation that takes,
you know, uh, 10,
uh, that's going to require you to do 10_10,
uh, floating point operations.
That's a lot, right? That's- that's, that's 10 billion.
And so on a typical computer,
let's make it a 10 giga flop computer,
but that means it's also we can carry out 10_10 flops per second.
And so we would guess that that's gonna take you about one second on that computer.
Okay. So let's look at the complexity of vector addition inner product.
We can also look at scalar vector multiplication. All right.
Let's look at adding two vectors.
So, uh, when we add two vectors.
Well, it takes n additions because you have to add each x_i to each y_i.
And there's n of those and entries.
So that's n flops total.
Um, an inner product that's forming,
that's calculating this x_1,
y_1 plus up to x_n, y_n.
Okay? Well, first you gotta multiply all these pairs and there's n of those.
So you're gonna have n multiplications.
And then you're gonna add them up.
Now when you add two numbers, that's one addition.
When you add three numbers, that's two additions.
So what do you add n numbers?
That's n minus one additions.
So you're going to have to do n
minus one additions and multiplications and altogether 2n minus one flops.
Now, no one would ever give them
minus one because it's- it's understood that this is very
crude and so people would always say that an inner product cost 2n flops.
In fact, a lot of people would even just say n because we're
not even shooting for a factor of two and accuracy here,
just n for the inner product.
Now, incidentally, this is interesting.
Now you can- now we can say something about if- if one of these vectors is sparse,
that can be a whole lot less.
For example, suppose x is sparse and y is not.
Um, x is sparse means that most of his entries are zero.
Now when I calculate the inner product,
I don't have to worry about those entries because all I'm gonna do is multiply x_i,
which zero by y_i.
Didn't matter what y is, I don't have to do it.
So the only turns out the only actually have to do is for every non-zero entry in x,
I have to multiply that x_i by the corresponding y_i and I have to add those up.
And so the complexity is- is around this.
It's twice the number of non-zeros in x.
Right. So this is an example of why you
might be interested in or care about sparse vectors.